Exploring

Joining Facebook!

2010-05-03T17:00:00.001-04:00

I'm really excited to announce that I'm going to be joining Facebook to work on the infrastructure team. With all the growth Facebook has seen comes unique challenges in scaling systems. I'm looking forward to working on this.

Of course, this also means saying good bye to Google and reCAPTCHA. It's been over 3 years since we started working on the crazy idea of getting millions of people to digitize the world's books in their spare time. I'm looking forward to seeing reCAPTCHA continue to grow.

Juxtapositions

2010-02-01T21:15:00.003-05:00

From time to time, reCAPTCHA will give users odd juxtapositions of words. I got quite a kick out of seeing this one:

I think this would make a great show!

Recipe: Double Chocolate Chip Peppermint Cookies

2009-07-10T21:43:00.003-04:00

This cookie is a nice variation on the classic double chocolate chip.

1/2 cup butter (one stick)
1/2 cup brown sugar
1/2 cup white sugar
1 egg
1/4 tsp vanilla
1/4 tsp peppermint
1 cup flower
1/4 cpu unsweatened cocoa powder
1/2 tsp baking soda
1/4 tsp salt

Directions

Preheat oven to 350F
Soften butter and mix with eggs, sugar, peppermint and vanilla
Mix flower, salt, baking soda, and cocoa in a separate bowl
Beat in the dry ingredients
Form balls on a cookie tray and bake for 8-10 minutes. Underbake slightly so the cookies are chewy

Tip: I've found that I'll eat these cookies far quicker than I really should. In order to ration the cookies, I will mix up a double batch, and freeze the balls of dough. Once the dough is frozen, you can place the balls in a ziplock bag. The cookies can be baked from frozen by adding 2 minutes to the baking time and last a few weeks. Cookies can then be baked in small batches. I can't tell any difference between cookies from frozen dough or fresh dough.

Laptop + Multiple Monitors Help

2009-01-14T14:26:00.002-05:00

I'm trying to get my laptop to display on dual external monitors. I'd appreciate some guidance in getting this configuration set up

What I have

A Dell Latitude D620 with nVidia Corporation G72M [Quadro NVS 110M/GeForce Go 7300]
A Dell docking station with dual-link DVI output
2 Dell 2007FP Monitors
Ubuntu 8.04

What I want

When I dock my laptop, the two external monitors are used (I don't really need to use the internal screen as a third monitor)
When my laptop is undocked, my internal screen activates.

Amazon's CloudFront CDN: disappointing

2008-11-18T12:46:00.002-05:00

I took a look at CloudFront today. They have really good intentions. The CDN space is quite a mess -- it could easily be a pay-as-you-go, self-service industry. However, players such as Akamai try to make a large profit. The CDN space is especially hard for small sites -- you can't get any reasonable pricing unless you are doing high levels of traffic.

Amazon wants to change all of that. However, I think they made a number of missteps in their initial offering.

They aren't using it on amazon.com. They use Level(3)'s CDN! Why should anybody consider using a service Amazon isn't using themselves. This is a chance to prove your CDN in real life.
Tiered pricing. In a self-service model, it doesn't make sense to offer different prices for different bandwidth usages. One customer with 100 TB of traffic is the same as 10 customers with 10 TB of traffic.
Pay per request. For S3, this made sense. Every request was one disk seek on the servers, and people need to pay for that. However, in a CDN, you are expected to serve from memory. The 1 cent per 10,000 requests effectively adds 6 KB of data to every file. So if you serve a 1 KB file, this increases your cost by 6x. At the very least, the fixed cost per request should be less than that with s3 to account for the lack of disk seeks
Lack of peering. Doing a traceroute to cloudfront from a few locations (Carnegie Mellon, colos in New York and LA), it appeared that all of my traffic was going over transit links. In contrast, traffic to amazon.com went over fast and cheap peering links.

I do hope that Amazon fixes up CloudFront. It's a fantastic concept. They have the power to force reason into the market.

More human computation with GWAP

2008-05-14T02:08:00.002-04:00

It's oh so exciting to see that GWAP (games with a purpose) has launched. GWAP is part of the research on human computation that started the reCAPTCHA project. GWAP is a framework which allows researchers to create fun games which generate useful data. For example, "Matchin" is a game where you and a random stranger on the internet get a pair of images. You must agree on which one is "better" without talking with each other. The game is fast, fun, and very addicting. From this game, you can actually get quite a bit of useful information. Most importantly, it's possible to find the "good" photos from a site like Flicker.

What I find most exciting about GWAP is that it is a production service. Many researchers will write papers about ideas, maybe create a prototype or a mock-up. However, they don't really do anything to bring their ideas to fruition. Luis's work is different. For example, with reCAPTCHA, we've spent months developing systems for serving CAPTCHAs to the internet. Most of this time was spent making our code reliable, scalable, and fast. Our efforts really payed off. reCAPTCHA now serves CAPTCHAs on a wide range of sites including Ticketmaster, Facebook, StumbleUpon, Twitter and Bebo.

I think this tendency for productionizing is going to pay off with GWAP. Lots of time was spent on things like UI design and scalability. The UI makes the games fun to play, the scalability makes sure that the team can have a real world impact.

Congrats to Mike and the rest of the GWAP team on a job well done.

Wanted: Temporary Palo Alto Housing

2008-04-01T21:54:00.002-04:00

I'm looking for 1 bedroom in area below between May 1 and Aug 20 (so hopefully, something furnished). Closer to the green arrow thingy is better. Please email me at bmaurer@andrew.cmu.edu if you have something like this.

The Open Source Google Stack

2008-03-26T15:40:00.000-04:00

The open source community is slowly growing a software stack that emulates a number of internal Google technologies. What's interesting is that the stack is being developed by a number of tech companies -- ranging from giants (mostly Yahoo!) to medium size firms (Facebook) to startup companies (Last.fm, PowerSet, Krugle, Veoh). So far, the following pieces of infrastructure have been developed

Hadoop is an umbrella project that covers a number of technologies: the Hadoop Filesystem (replacing Google's GFS), Map-Reduce, and HBase a database inspired by BigTable. In short, Hadoop covers storage technology as well as the infrastructure needed to compute over large amounts of storage.

Thrift is a RPC system which was initially developed by Facebook. While, in some senses, there is no lack of RPC-subsystems out there, Thrift is different. Thrift focuses on inter-language RPC. Interop between a large number of languages is transparent. Thrift also avoids the bloat that comes with some of the older RPC systems, such as SOAP. Finally, Thrift doubles as a serialization system (sort of like Python's Pickle or Java serialization). Because the binary data it generates is compact, it can be used for logging or in a database. Thrift is partially modeled off of Google's Protocol Buffers.

ZooKeeper is a service for coodination between distributed servers simplifying functions such as master election, configuration lookup, and distributed locks. ZooKeeper was recently open sourced by Yahoo.

These projects seem to be the start of a positive trend: a number of companies are realizing that in order to rapidly develop new services, they need to have infrastructure. In contrast to Google's typical strategy, these companies are sharing their work with each other. I think that this collaboration is critical to developing a robust infrastructure.

In some ways, I think that these developments put Google in a tough spot. It's not unforeseeable that these open source stack will grow to point where it is superior to Google's own stack. It would be unrealistic for Google to migrate to these new technologies. If there's going to be an open version of Google's technology, it would be in Google's best interest for that implementation to be their own. Not only would Google benefit from external improvements to their stack, it might make it easier for them to acquire new startups and integrate their technology into Google.

Silicon Mechanics

2008-02-18T11:05:00.002-05:00

I'm looking at Silicon Mechanics for potentially buying a few rack mount servers. I'm wondering if anybody has good (or bad) experience dealing with them.

On paper, it looks like they have prices that are much cheaper than Dell (of course). Also, they have a nice thing where they can have two servers in a 1U (16 cores in a 1U... that's alot). I just want to see if anybody here has some real experience with them.

Windows Error Messages

2008-02-06T10:18:00.000-05:00

While being out of disk space on a server isn't generally much fun, this error message made it worth the while

Randall Munroe (xkcd author) comes to CMU

2007-11-10T17:00:00.000-05:00

Randall Munroe came to CMU to give a talk yesterday. It was the most attended talk of the semester. Randall's talk was fantastic -- he said that he is trying to fill part of his bedroom with plastic balls (like in one of his cartoons). He also drew two mini-cartoons while talking, which was very cool. Finally, he set two very useful standards. First, he declared that punctuation need not go inside quotation mark (eg, did she say "I love you"?). Second, he declared himself president of the Internet (so that another evil person wouldn't take it.

I guess what I really like about Randall's talk (and about XKCD) is that it's a way to relax and reflect on being a tech person. It feels like The Daily Show for geeks.

New reCAPTCHA APIs: i18n and Theming

2007-11-08T14:10:00.002-05:00

We're really proud to announce the release of two new APIs for the client side.

Internationalization For users of our default theme, we've added a way to request the display of the user interface in a different language. We've translated our UI and help page into the following languages

German
Spanish
French
Dutch
Portuguese
Turkish
Russian

We're looking into getting translations for other languages. If your language isn't supported, you can use the theming API to allow you to customize the user interface.

You can take a look at an example of internationalization at: http://recaptcha.net/fastcgi/demo/recaptcha?lang=ru http://recaptcha.net/fastcgi/demo/recaptcha?lang=es

Theming The ability to customize the appearance of reCAPTCHA has been a frequent request. Our Theming API allows you to completely customize the way reCAPTCHA looks. For example you can see a demo at:

http://recaptcha.net/fastcgi/demo/customtheme

In this demo, we show how you can completely remove the UI of reCAPTCHA and make a non-themed interface. You can use this as a starting point for blending reCAPTCHA into your site.

More information To get more information about these new APIs, look at our client API guide:

http://recaptcha.net/apidocs/captcha/client.html

Updating Ubuntu -- please make it faster

2007-10-18T20:10:00.000-04:00

Dear Ubuntu hackers,

Gusty is out. I want it. But the update process for your wonderful operating system is broken. It seems that this process on getting files from a central machine. Said machines seem to be overwhelmed by other users who also want to upgrade -- they won't even respond to a TCP SYN packet

In the future, it'd be really nice if this process used mirrors so that it wouldn't be as flooded.

If the file really does need to be centralized, choose the host carefully. S3 is very good at this stuff. Akamai does even better (though they'll charge you an arm and a leg).

PS: now that I got past accessing that server, Gusty is downloading at 4 megabytes per second, thanks to Internet 2. It would have been a lot fast if it used the mirror for that one small part

XKCD teaches SQL Injection

2007-10-10T00:45:00.000-04:00

The hacker inside me found this funny

Randy Pausch: an inspiring video

2007-09-21T19:56:00.000-04:00

Randy Pausch is a professor at Carnegie Mellon who believes in making programming, specifically for entertainment purposes, accessible to everybody. Sadly, Professor Pausch has an untreatable form of cancer which will take his life in the next few months. This week, he gave a talk which is truly inspirational. This is a person I wish I could have gotten to know.

M-x gdb

2007-09-21T11:34:00.000-04:00

I really wish somebody had told me about this a long time ago:

Firefox Caching

2007-09-04T16:29:00.000-04:00

Federico posted about some work he was doing on making Firefox not cache as many uncompressed bitmaps in memory. I was playing around with the cache stuff and noticed something: my Firefox cache is full of youtube videos. YouTube videos aren't exactly the best thing for Firefox to cache. My internet connection is fast enough that streaming the videos works just fine. I suspect that most people who use online video frequently do so on a connection that can support streaming (otherwise, YouTube would be painfully slow, and they'd go do something else).

It turns out that Firefox's cache is based only on least-recently-used. So, let's say you have a 50 MB cache. Right now, all 50 MB of it is full with cached javascript, css, images, etc. You go to youtube and start watching a 10 MB movie. 20% of your cache gets blown away. In all likelihood, you'll never view that video again.

Even worse is if you listen to a flash-based media player. The MP3s that this downloads are cached just like anything else. So if you listen to 50 MB worth of music your disk cache gets blown away.

Probably LRU isn't the best technique to use here. I'm not sure how one would evaluate various choices (what is a representative test set of browsing sessions?)

Yay Dual Homing!

2007-08-30T19:53:00.000-04:00

Today, we had our first drill with dual homing on reCAPTCHA. In Pittsburgh, the water main that serves the Carnegie Mellon area broke today, causing a complete water outage on campus. This has resulted in many servers being shut down. reCAPTCHAs servers were kept up, as they are production servers, however we were told that it was possible they'd be shut down.

It's times like these when you just love having a backup. We have a DNS service that does automatic health checking and routes away from unplanned outages. However, with DNS it takes a few minutes for these sorts of changes to take affect. We proactively switched away our traffic off of the pittsburgh servers.

One of the funny things about using DNS for Dual Homing is how long it takes to really kick in. We're still getting requests to our pittsburgh servers even hours after we made the switch. This is one reason it's important to have DNS not be the only load balancing solution (you need a L7 or L4 load balancer as well)

Facebook 2.0

2007-08-28T15:42:00.000-04:00

So if your profile says you are single, and looking for women, single women looking for men might soon get a higher ranking in search results? I'm not sure what other "intentions" facebook might know about

Of course, this could open up a whole new era of social networking: I'd call if AdFaces. If you feel that you are not showing up often enough in search results, you can bid for clicks on your profile with a CPC model. Or maybe Facebook can experiment with a cost-per-action model. Then we'll need a product like Facebook Analytics to improve profile conversion rate, and FaceSense to allow publishers to embed targeted profile advertisements on their website.

Making bugs... and fixing them

2007-07-17T01:13:00.000-04:00

Two interesting bugs from today.

First, you gotta be careful with order of operations. I wrote this code:

int someValue = ...;
storePref(MY_PREF_NAME, "" + someValue + 1);

The code looks innocent enough. However, order of operations kicks in here. The compiler translates this as: (("" + someValue) + 1), or Integer.toString(someValue) + Integer.toString (1). So rather than adding one, we multiply by 10 and then add one :-). The fun part about this experience was that I had Neal Gafter sitting next to me to explain exactly what I'd done, and also to point out where this problem is discussed in his fantastic book Java Puzzlers (Neal gave me a copy, which I've been meaning to read).

In the "Fixing bugs" column, I was testing something out on IE 5.0 today (yes, five-point-oh, released in 1999. Sadly, it sill has some market share). The box had Google.com as the homepage, and I noticed that it displayed a JavaScript error (for older versions of IE, displaying this error was a default setting). After reporting this, it turns out that it was actually an interaction with Google Desktop. Now, I don't expect that there are that many users with IE 5.0 and Google Desktop, but with millions of users, "not a lot" means thousands or tens of thousands of people.

Yahoo's and Microsoft's CAPTCHAs likely NOT broken

2007-07-10T19:39:00.000-04:00

BitDefender went a bit overboard in their claim about CAPTCHAs. Their statement about CAPTCHAs was issued as a press release (which clearly has meet their goals of getting press -- regardless of the accuracy of their statements). The article states that about 500 accounts are being created per hour. This is about the effort of one person solving CAPTCHAs. If they had actually broken the CAPTCHAs of Hotmail and Yahoo, there would be tens of thousands of accounts every hour. The article also mentions that about 15,000 accounts has been created. At 2 cents per CAPTCHA, that's a $300 investment to manually solve the CAPTCHAs (this rate is easily obtainable in some countries). It's extremely unlikely that one could hire a person to break the CAPTCHAs of Yahoo and Hotmail for this price. Also, if you're working on a virus-type program, one of the easiest ways to generate CAPTCHA solutions would be to use your infected users (eg, make them type in a CAPTCHA once per day. If you integrate it into the web browser, it might not raise suspicion).

The information that BitDefender has published actually suggests that these spammers/virus makers have not beaten CAPTCHAs using OCR

Life at Google

2007-06-27T14:42:00.000-04:00

This blog is pretty funny. It's sort of like what the Daily Show might say about Google -- the facts are mostly true (some are pretty out-dated), but they're twisted in the opposite direction of how things actually are.

The blog entry got me thinking about what I like and don't like about an internship at Google. One of my favorite things is the freedom to set my own hours. I personally have an aversion to waking up any time before 10am. Usually, I wake up, read some blogs, check personal email and reCAPTCHA support email (I can't check Google email remotely as an intern), then I walk to work around 11:30-12:30. Having the free meals every day (I rarely get to take advantage of breakfast, which ends at 9:30) is a huge plus. The blog article hinted at the end how huge of a factor the free food actually is. It's a relatively inexpensive perk that makes a huge difference.

The comments about how the developer's work areas are laid out is also really interesting. The first time I saw the Google layout, I was a bit surprised. "I thought I was getting an office!". I ended up really liking this in the end. Before Google, when working on the Mono project, the primary way to communicate with other people was IRC. When I had to ask a question, sometimes it wasn't always possible to get a response right away. At Google, my coworkers are sitting very close by. I can work something out on a whiteboard with them. I don't have to walk a long way to their office.

One thing the article didn't mention (probably because it's a problem that's worse at MSFT than Google) is that going into a big environment like Google can be intimidating. With open source, building things was always easy. ./configure; make; make install. The process takes about 10 minutes the first time, 2-3 minutes every day, depending on how many changes. At Google (and I'm sure pretty much any place similar), checking things out can be an adventure. A simple build process is probably an advantage of working on an open source project, or at a smaller company.

At the end of the day, the thing I really enjoy about Google is the access to the vast repository of interesting code Google has to offer. Being able to see how a Google product works, under the hood, is just an amazing experience. I remember going snorkeling on an 8th grade trip to the Bahamas. The excitement of being able to see ocean life for the first time is very similar to my experience of being able to look into the moving parts of Google. Surely this isn't something unique to Google. I'm sure there are as many fascinating moving parts inside Microsoft, or many other large companies.

On another note, the reCAPTCHA launch went fantastically well. I was happy and relieved that we didn't have any embarrassing incidents like crashing under the load of Digg (Our servers handled it just fine!). We've had some exciting customers adopting our product. I hope to write more soon.

NYTimes Article on CAPTCHAs

2007-06-11T04:08:00.000-04:00

The New York Times is running an article today on CAPTCHAs. The article really misses some key points. For example, it talks about the CAPTCHAs on YouTube. YouTube's CAPTCHA is really, really bad. The CAPTCHA is mis-designed, using different colors to attempt to provide security. I can't imagine solving this as a color blind user, it must be nearly impossible. Most CAPTCHA providers have migrated to using a monochrome CAPTCHA (for example Google, Yahoo and MSN). The way to create a challenging CAPTCHA today is to make segmentation difficult. This can be achieved without causing as much pain for humans.

Then there's this Asirra thing. Did anybody from the Times actually try it? Here's an unscalled image of what it looks like:

Now, you can hover over an image for a larger version. But now to solve one of these CAPTCHAs, you've got to hover over 12 images, and make a decision on each. Asirra is undeniably cute, but it's not clear that it's all that much easier than the current, well designed, CAPTCHAs. The security of Asirra is also unclear. It'd be interesting to see what happens if Asirra is ever put in front of a high value target (something that can be used to send email, host pagerank-gaining links, or host porn/warez). I have a feeling that some spammer would find a way to abuse a botnet and take advantage of some of the design issues in Asirra.

reCAPTCHA: A new way to fight spam

2007-05-23T16:31:00.000-04:00

You've probably seen a CAPTCHA before. It's those funky letters you have to enter before you sign up for an account on almost any website. I'm proud to announce a new type of CAPTCHA: reCAPTCHA: (click to see a live demo!).

You might notice that reCAPTCHA has two words. Why? reCAPTCHA is more than a CAPTCHA, it also helps to digitize old books. One of the words in reCAPTCHA is a word that the computer knows what it is, much like a normal CAPTCHA. However, the other word is a word that the computer can't read. When you solve a reCAPTCHA, we not only check that you are a human, but use the result on the other word to help read the book!

Luis von Ahn and myself estimated that about 60 million CAPTCHAs are solved every day. Assuming that each CAPTCHA takes 10 seconds to solve, this is over 160,000 human hours per day (that's about 19 years). Harnessing even a fraction of this time for reading books will greatly help efforts in digitalizing books.

reCAPTCHA provides an easy to use API for putting CAPTCHAs on your site. Installing is as easy as adding a few lines of code to your HTML and then making a HTTP POST request to our servers to verify the solution. We also wrote plugins for WordPress, MediaWiki, and phpBB to make it very easy to integrate.

One other interesting service reCAPTCHA provides is a way to securely obfuscate emails. Many sites display emails like bmaurer [at] foo [dot] com or use hacks with tables, javascript or encodings to get the same effect. Spammers are getting smarter and figuring out these tricks. Spammers are especially diligent at working around the strategies of well known open source software. Consider this warning on bugzilla.mozilla.org:

Although steps are taken to hide addresses from email harvesters, the spammers are continually getting better technology and it is almost guaranteed that the address you use with Bugzilla will get spam.

reCAPTCHA Mailhide provides a scalable solution to email obfuscation that can be widely deployed without being breakable. Mailhide provides a way to encrypt a user's email with a key only reCAPTCHA knows. reCAPTCHA will only display the email address when the user solves a CAPTCHA. With reCAPTCHA, I can display my email address as bmau...@andrew.cmu.edu. If you click on the three dots and solve a CAPTCHA, you can see my address. Mailhide provides a way for individual users to encode their email address as well as an API for services (like Bugzilla) to share an encryption key with reCAPTCHA.

If you're suffering problems with spam, take a look at reCAPTCHA. Not only can you solve your problems with spam, you can help preserve mankind's written history into the digital age!

LD_LIBRARY_PATH empty entries

2007-05-14T15:30:00.000-04:00

Many of us developers have a bashrc that has lines like:

LD_LIBRARY_PATH=$LD_LIBRARY_PATH:$HOME/install/lib

I've always known that this isn't perfect, that one should check $LD_LIBRARY_PATH isn't empty, but had always thought it was just a minor point. It turns out that the loader sees an empty entry as meaning the current working directory. This means that it looks there for libraries.

The reason I noticed this is because I was using sshfs to mount something on my workstation in Pittsburgh from my laptop in California. When I ran any command (for example "ls"), the loader would look for tons of libraries. Each one of these libraries, it'd execute a stat for. A round trip between Pittsburgh and California is 90ms... so you can imagine everything was quite slow.

Of course, there are security implications too. I'm not that worried about a rogue directory on my laptop, but on shared systems (such as some of the university ones), I can imagine this being a risk.

In the Bay Area...

2007-05-09T01:36:00.000-04:00

Starting this Saturday I'll be in the Bay Area, specifically Mountain View, for my internship at Google. While there, I'll be working on Google Calendar.

A new spam technique

2007-04-05T15:33:00.000-04:00

A spammer got very clever in terms of ways to make money

Subject: Search on Google raise money for charity Dooniz is now affiliated with Google. That will permit to redistribute a part of the money made on Internet to charity foundations. Internet users can make a difference by search Google using Dooniz.com. A simple click can help children in difficulty or bring more money to cancer or climatic changes researches

This person basically created a homepage with loads of affiliate links, and claims that it helps charity (the site says 75% goes to charity. Yeah, right). Primarily, Google is advertised (using the site specific search stuff that AdSense provides). People get convinced they are helping charity when very little of the money, if any, will actually go that, make it their homepage, the dude profits.

Hopefully, Google will prevent the guy from cashing in on spamming...

Google Job Ads

2007-03-30T11:22:00.000-04:00

Google likes to advertise job positions with Adwords. I was searching for something about the HTTP protocol and encountered this Google ad:

Nice to see a sense of humor in the ad

Gnomefiles needs love

2007-03-02T17:05:00.000-05:00

Eugenia Loli-Queru sent me a quick note today that GNOMEfiles is in need of an owner. The site gets 25,000 pages daily on average. This seems like a pretty important resource for the GNOME community, something worth keeping.

Google's CAPTCHA Broken?

2007-02-28T22:44:00.000-05:00

A few months ago, I found a nice trick that let me read comments on my blog without polling for them. GData allows you to get a ATOM feed of comments on your blog. For example mine is: http://bmaurer.blogspot.com/feeds/comments/default I put this in to Google Reader and blog comments show up just like any other type of blog entry. Recently, I've noticed that, from time to time, I am getting spam comments. However, Google uses a CAPTCHA to protect it's comments. This means one of two things:

Google's CAPTCHAs have been broken
Some spammers are willing to hire humans to break CAPTCHAs

The rate at which spammers post is very small, maybe one or two comments per month. I think this might support a theory that spammers are using humans (if they were using computers, I think it'd be easier to post on the blogs more often). However, Google may be using anti-spam filters in addition to the CAPTCHA (this would be easy enough for somebody to verify, just copy and paste some blatent spam in to blogger, and solve the CAPTCHAs). To be honest, I don't think blog spam would make enough of a profit to justify humans. Google is using the nofollow tag, so the links don't get any PageRank. I bet that spammers are able to break Google's CAPTCHA with a <1% href="http://www.ceas.cc/papers-2005/160.pdf">this paper from Microsoft Research on the importance of segmentation in CAPTCHAs).

CMU dorm policy: Nerds gone wild?

2007-02-28T14:04:00.000-05:00

Recently Carnegie Mellon announced that it was going to test out a gender neutral housing program next semester. It's hard to see how this can be all that shocking (most university housing is co-ed by room). Of course, there's always somebody with an ridiculous point of view:

Unfair or not, my fear is that nerdy kids at Carnegie Mellon might put aside writing computer language for the space program and attempt to brush up their knowledge of biology in the privacy of their own dormitories. This is wrong. Nerds should not be having love affairs with other nerds. There is always the danger that in the throes of nerd passion, their thick glasses will collide or else they will drop heavy laptops onto vulnerable body parts. [CMU Dorm Policy: Nerds gone wild?]

I'm glad to hear that some folks think of students at CMU as nerds who need to be protected from distractions such as members of the opposite sex.

Big Media DMCA Notices: Guilty until proven innocent

2007-02-07T12:05:00.000-05:00

It's no secret that media companies have started to hire companies such as BayTSP to automatically find file sharers and send letters to their ISPs. The goal of this is to use fear to persuade people to use legal methods of getting digital content.

Many ISP's, especially universities, trust the good faith of these companies and will automatically deactivate the Internet connection of those who they get notifications for. As a personal project, and with the help of Carnegie Mellon's Information Security Office (which employs me to work on various computing security tasks), I decided to investigate the reliability of notices from companies such as BayTSP. The answer: the companies do not actually gather the data they claim to. Their standards for sending DMCA notices are very low.

In order to understand the issues, it's first necessary to have a basic understanding of BitTorrent. In order to download something via BitTorrent you download a ".torrent" file from any number of sites that index the content. This file contains a fingerprint for every piece of the file that you are attempting to download. It also contains a reference to a tracker. This tracker is the way that peers (the people downloading the content) find each other. After contacting the tracker, you contact each of the potential peers that the tracker shares with you (and other peers may contact you). The client then begins swapping parts of the file with each of the peers. What the media companies object to is that in the process of downloading the file, your client will offer parts of their copyrighted content to other users -- a violation of copyright law. In order to catch these violations, BayTSP advertises fake clients to the Bittorrent tracker and uses the list of peers which it gets back to find violations

For my investigation, I wrote a very simple BitTorrent client. My client sent a request to the tracker, and generally acted like a normal Bittorrent client up to sharing files. The client refused to accept downloads of, or upload copyrighted content. It obeyed the law.

I placed this client on a number of torrent files that I suspected were monitored by BayTSP (For my own protection I don't want to identify the torrents used for this research. I used the fact that NBC is a client of BayTSP to find trackers. If you want to check if BayTSP is monitoring a torrent, look for IPs coming from ranges in test.blocklist.org). Because the university's information security office is very diligent about processing DMCA notices, I would be able to tell if the BayTSP folks sent notices based on this. With just this, completely legal, BitTorrent client, I was able to get notices from BayTSP.

To put this in to perspective, if BayTSP were trying to bust me for doing drugs, it'd be like getting arrested because I was hanging out with some dealers, but they never saw me using, buying, or selling any drugs.

The fact that BayTSP does not confirm that the client it is accusing actually uploads illegal content could cause false identification of innocent users. BitTorrent trackers work via a standard HTTP request request, for example:

GET /announce?info_hash=579CC43E4D66D35AE22312985EA04275939AB477&peer_id=asdfasdfadfasdf&port=12434&compact=1

One easy way to make somebody look likea bittorrenter would be to get them to go to a website with the code <img src="http://tracker.com:12345/announce?info_hash=579CC43E4D66D35AE22312985EA04275939AB477&peer_id=asdfasdfadfasdf&amp;amp;port=12434&compact=1" />. They'd be on the tracker, and BayTSP would see their IP address, and might send them an infringement notice. BayTSP might check that they are listening on the port they advertise (maybe even check for a BitTorrent handshake). If the user is using bittorrent for legal usages, you could just advertise a port they were listening on. More investigation is needed into exactly what triggers the notice.

One even easier trick you can use: the BitTorrent clients BayTSP uses support Peer Exchange. You can give them the name of another peer for them to rat out to the ISP.

At the end of the day, BayTSP (and probably other similar companies) are sending DMCA notices which claim that they detected a user uploading and downloading copyrighted files. This is a lie. They didn't catch the user in the act of downloading. A lying tracker, a peer using peer exchange, hostile web page, or buggy BitTorrent client could all result in a false DMCA notice.

If your ISP forwards a DMCA notice from these guys, point them here. This research suggests that they have no evidence of wrong-doing. If ISPs learn that the folks sending them DMCA notices are not being completely honest, they may be willing to reconsider their position about how they respond to the notices. The people I work with at Carnegie Mellon seemed willing to reevaluate their policies given this evidence. I believe that ISPs should require that any peer-to-peer related DMCA notice include a statement regarding exactly what evidence of sharing was found. Ideally, the notice should contain evidence that could be corroborated with log files (for example, "we found that the client at 123.1.2.3 uploaded 1 MB of file X to 4.3.2.1". The ISP may be able to check that there was 1 MB of traffic between these two clients).

A piece of good news for anybody who has gotten a bittorrent related notice from BayTSP: it doesn't seem like a studio could do much in terms of court action with the evidence BayTSP gives them.

For the technically minded, I though I'd share some observations of the behavior of BayTSP's clients

BayTSP's clients don't don't accept incoming connections, only send outgoing ones. I wonder what exactly this is for.
Some of the BayTSP clients claim to be using Azureus (and support Azureus extensions), while others run libtorrent. I'm not sure why they are doing this
When BayTSP's clients connect to a BT user, they claim to not have downloaded any of the file, but refuse uploads. Not only does this behavior not make any sense for an actual user, but it seems like BayTSP would want to accept data, which might provide proof of infringement.
Some of the IP ranges I noticed coming from BayTSP were: 154.37.66.xx, 63.216.76.xx, 216.133.221.xx. Sometimes, they make themselves really obvious on the tracker. For example, 154.37.66.xx and 63.216.76.xx will send 10 clients to the same tracker all claiming to listen on port 12320. Maybe trackers should block these folks

Interning at Google Again

2007-01-18T16:23:00.000-05:00

This summer, I'm going to do another internship at Google. I'll be working on Google Calendar.

Beware random CAPTCHAs found on slashdot

2007-01-01T15:02:00.000-05:00

This CAPTCHA, found on slashdot is pretty silly. First, the HTML doesn't really provide that much security. It wouldn't be that hard to script Gecko to render the thing. Worse, it has a very insecure implementation:

if (isset($_POST['hash']) && isset($_POST['CaptchaStr']) ) 

{

 if($captcha->validate_submit($_POST['hash'],$_POST['CaptchaStr']))

  $Message = "Correct.";

 else

  $Message = "Incorrent.";

}

  function check_captcha($correct_hash,$attempt)

  {

   // when check, destroy picture on disk

   if(file_exists($this->get_filename($correct_hash)))

   {

    $res = @unlink($this->get_filename($correct_hash)) ? 'TRUE' : 'FALSE';

    if($this->debug) echo "\n
-Captcha-Debug: Delete image (".$this->get_filename($correct_hash).") returns: ($res)";

   }

   $res = (md5($attempt)===$correct_hash) ? 'TRUE' : 'FALSE';

   if($this->debug) echo "\n
-Captcha-Debug: Comparing public with private key returns: ($res)";

   return $res == 'TRUE' ? TRUE : FALSE;

  }
  /** @private **/

  function get_filename($public='')

  {

   if($public=='') $public=$this->public_key;

   return $this->tempfolder.$this->filename_prefix.$public.'.jpg';

  }

So, here are a few bad things you can do

If your OCR can read 1/2 the chars on the page, the md5sum lets you crack the others. Really quickly
Forget OCR. It doesn't check that the server itself generated the hashes. Hash "apple" then submit the hash and the word "apple".
There are no checks for duplicates. You can solve one captcha and submit it 1000000 times.
You can delete any jpeg file on the website, due to the non-checking of the hash for the word ".."
You can fill up the dude's disk by requesting lots of captchas but not solving them

Don't trust this kind of script!

Posting Zero-Day Scripting Exploits

2007-01-01T14:15:00.001-05:00

It's really sad to see people posting zero day exploits for large applications, such as this GMail exploit. First, it's not clear what this guy's motives are. Maybe he wants to get slashdotted so that the ads on his page will get clicked due to the massive number of visitors. He might also want to get a bit of fame, which is easier to do if you post a zero-day issue and then get it slashdotted.

Maybe he just wants the security issue fixed as fast as possible, and having notified the Google security folks is unsatisfied with their response time. If that's the case, I think he was very irresponsible in the posting of the exploit. First, it's new year's day. That means response time from any website is going to be slow. Thus, it will take longer to get something pushed out. Why not publish something like this on a weekday, when people are at work? The issue will be fixed faster, and slashdot traffic will be higher (more ad clicks, more fame!).

It's also worth noting how dangerous such zero-day issues are. Spammers could do quite a bit of damage in a short amount of time (even if it was open for an hour or two). Spammers likely have (or will acquire) pages that get a fair number of clicks (domain landing pages and porn sites are likely good candidates for this). A zero day exploit could easily let them gather some great data for spamming (Imagine being able to send out an email to somebody from one of the people on their contact list, including the full name of the person! It's a spammer's dream come true).

With all that said, I think the use of JSON for things like sending contact lists is becoming a large danger. I've found and reported similar issues to Google and Facebook in the last month. I bet lots of web 2.0 sites have the exact same issue. There are two easy and secure ways to fix the issue

Use a secret token. For example, make the url something like google.com/contacts?tok=asdfasdfasdfasdf. Make the tok a per-user string (like a HMAC of their username). If the tok isn't correct, deny the request
Rely on XmlHttpRequest. Insert the following code at the top of the JS document "while (1);". Using XmlHttpRequest, download the code, and remove the token. People trying to use a script tag to include the document won't be able to do so.

Performance Tip of the Day: Script Tags are Blocking

2006-12-04T17:32:00.000-05:00

Today I downloaded the fantastic firebug extension. It has a mode where it shows network activity:

I learned that if you have a JavaScript file, the browser will block rendering of the page until the request is done. I saved about 100ms on a few sites I run by moving the Google Analytics tracker to the bottom of the page (not sure why it wasn't being cached, probably because I am on an SSL site).

Posting sensitive data in JSON

2006-11-28T13:12:00.000-05:00

If you are using JSON in AJAX, make sure not to put sensitive data in the JSON feed. Because script tags don't follow the same-origin policy, it's possible to include a script from third party sites.

Google's GData-JSON feeds (which I blogged about earlier) had just such an issue. Google allowed you to request a URL such as http://www.google.com/calendar/feeds/default/private/basic?alt=json-in-script. If you use Google calendar, take a look at that feed with the alt= part taken off. It likely has your email address, your full name, and possibly some sensitive events in it. Any site you visited could have requested that URL and scraped the data. Note that with more advanced techniques, it's possible to get data that doesn't use the callback, ie, array literals. See Jeremiah Grossman's blog

Luckily, this was fixed relatively quickly after I reported it.

DomBuilder + Functional Programming == Awesome

2006-11-25T13:27:00.000-05:00

The DOM sucks. It's so so slow to type document.createElement and document.createTextNode. One nice solution for this is DomBuilder which allows you to say:

document.body.appendChild(
 DIV({ id : "el_" + times, 'onclick' : 'alert("sdsdsd")'}, 
  STRONG({ 'class' : 'test' },"Lovely"), " nodes! #" + times
 )
);

When using the DomBuilder in a project of mine, I found that it couldn't handle data very well. I had a list of items, and I wanted to make a table. There's no easy way to do that with DOMBuilder.

However, a bit of functional programming can save the day. Using Prototype, and adding the following line of code to tagFunc gets lots of millage:

arguments = $A(arguments).flatten ().compact ();

What is this doing? First, we turn arguments into an array so that we can handle it cleanly. Then we flatten any arrays (turn [a,[b,c]] into [a, b, c]) and then compact any null entries ([a,null,b,c] into [a,b,c]). What's the win? Now this library can handle data very elegantly:

var stocks = [{ name : "NOVL", price : 6.28 }, { name : "GOOG", price : 505.00 }];
document.body.appendChild($table (
   $tr ($th ("Name"), $th ("Price")),
   stocks.map (function (stock) {
       return $tr ($td (stock.name), $td (stock.price.toString ()));
   })
));

Note the use of map to handle each of the stocks. Without the flatten, this would not have worked. It's pretty easy to build up HTML from data like this very elegantly.

Using GCal JSON to make a free/busy schedule

2006-11-22T23:44:00.000-05:00

Lately, I seem to be getting lots of emails of the form "When are you free this week, I'd like to meet with you sometime". Each time I get this email, I have to go to my calendar, copy my appointments for the next week, and send it in a reply.

In an ideal world, I could just paste a link to my calendar in iCal format. Sadly, not enough people use a calendaring client for this to be reliable (and worse off, many of the people I interact with use the horror that is Oracle Calendar, which doesn't really handle external ical).

This week, Google added JSON output to their Google Calendar feeds. This allows me to make a pure-javascript solution to this problem. I created a bit of Javascript code (here) which loads my calendar in JSON format and tells the other person when I'm busy

It's nice to be able to only show a free-busy projection of my calendar (I don't want the world to know who I'm meeting with, where I am, etc at every moment. I also use the calendar as a place to dump event related date, for example, airline confirmation numbers). I also like that I only have to host a small static html page to do this. No figuring out where to put a PHP script, no SQL, just a bit of javascript

TODO:

Handle multi-day events
Better date formatting (use day of week, month names, etc)
Combine events (If I'm busy from 10:30-11:30 and 11:30-12:30, I can just be busy between 10:30 and 12:30)
Not depend on prototype (or only take what I need)
Make it pretty

Now that javac is open source...

2006-11-13T16:10:00.000-05:00

Maybe somebody (me?) can finally make a patch for this issue:

[bmaurer@omega ~]$ cat x.java
public class x {
        public static void main (String[] args) {
                System.out.println ("hello world");
        }
}
[bmaurer@omega ~]$ time javac x.java

real    0m0.766s
user    0m0.604s
sys     0m0.040s

For the record, mcs has a time of:

[bmaurer@omega ~]$ time mcs x.cs

real    0m0.483s
user    0m0.440s
sys     0m0.024s

But Java is using a form of Ahead of Time compilation (they call it class file sharing or something) while my MCS is not.

Don't echo back plain text passwords

2006-11-01T22:14:00.000-05:00

Today I found two nice little security issues on an e-commerce site I use. First, the site has a page that allows you to change passwords. The code on the page is of the form <input type="password" name="password" value="MY PASSWORD IN PLAIN TEXT">. Secondly, the site had some Cross Site Scripting issues. At the end of the day, it was drop-dead easy to phish for people's passwords. Yikes.

Never, ever, ever echo sensitive data back to the user. It makes an XSS attack really damaging (and is also bad if somebody leaves their computer unlocked).

Finding Social Security Numbers with Google

2006-10-28T01:56:00.000-04:00

Google has a helpful syntax x..y for searching web pages with numbers between x and y. This feature, combined with the stupidity of the general public, results in social security numbers being findable: inurl:resume ssn * 10000...99999999.

Note that Google proactively protects users by forbiding the query 100000000..999999999 (that's the full SSN range). It also bans a varity of searches for credit card numbers. However, using the wider range allows one to still find socials, granted with some false positives.

Math.abs Returns a Negative Number

2006-10-18T17:00:00.000-04:00

Math.abs (Math.Abs in C# :-) is one of those methods that sould be pretty simple, right? Just take the value, if it's negative, return a positive version, duh! Well, it's not that simple.

There are 2³² possible values of int, each of which is positive, negative or zero. There's only one integer that is zero, namely 0x00000000. That means that either there is one bit pattern of ints that doesn't represent an integer, or there is not a 1-1 mapping between positive and negative numbers. It turns out, the second is the case. The odd number is int.MinValue, which is equal to 0x80000000 in binary.

What happens when you negate this number? In two's complement -x=~x+1. ~x = 0x7fffffff. ~x+1=0x80000000. That means -int.MinValue == int.MinValue. Uh oh!

Enter Math.abs. What's the function to do when passed int.MinValue. Well, in C#, Math.Abs throws an OverflowException. Java, on the other hand, happily returns int.MinValue. Either way, the caller of the function probably wasn't expecting this.

I discovered this oddity when reading Effective Java (kindly provided to all Google Engineers). The book talks about the code: Math.abs (new Random ().nextInt ()) % n as a way to generate random numbers between 0 and n. This code usually works, except when Random happens to return int.MinValue. In this case, the abs returns a negative value, causing the modulus operator to return a negative number. Eeeek!

At this point, I realized that for the data structures course I TA, many students used a similar piece of code in a hashtable they wrote. I wrote a quick script to check how many people screwed up on int.MinValue. Most students did.

I wondered how much this occurred in production code. Luckily, I had one of the best test cases at my fingertips. Google has an internal "grep" tool (the inspiration for the new Code Search) utility. I made a quick regex to find where this occurred. There were many instances.

Now that Google has released an external version of this tool, you can see some of the places this anti-pattern is used in the real world:

Each of these snippits is a time bomb. One in 2³² executions, the function will do something strange.

Having found this issue in Google's source code, I emailed somebody inside Google who had been running FindBugs internally. He in turn talked to Bill Pugh, who added a detector. I added a test case to the test suite for the homework assignment at CMU, so students will have to handle this case. All in all, a very obscure bug

So, what should you do rather than Math.abs? I've seen primarially two buggy patterns:

Hashtables People want to find "which bucket should I put an object with hashcode x in". The best way to do this is (o.GetHashCode () & 0x7fffffff) % table.Length. This has the advantage of being faster than Math.abs (no branches).
Random Numbers People want to say Math.Abs (new Random ().Next ()) % N. Not only is this buggy in the rare case, it can also cause a bad distribution of numbers for large N. Use the Next (int, int) method which allows you to specify bounds

Edgy Memory Usage

2006-10-07T12:28:00.000-04:00

I just installed the Ubuntu Edgy beta on my laptop. I'm impressed by the memory usage. On startup, it's using 87mb of ram. WOW.

In system monitor, there's one sore point. This system-tools-backend thingy is launching perl on startup. This requires 9 mb of writable memory on startup. What the hell is this thing?

Whatever the program does, it clearly does not have a reputation for performance. Ryan "kill wakeups" Lortie reported that the program made 20 wakesups per second

Filed a bug

Mono Summit; New Google Products

2006-10-06T11:16:00.000-04:00

Mono Summit: I'm going to be at the Mono summit in Boston (thanks Mig!). I look forward to seeing lots of Mono hackers (and having some very good ice cream :-)

New Google Products: In the past month or so, Google has had a pretty crazy schedule of product releases.

Blogger Beta: Google finally made lots of improvements to Blogger, giving it tags, etc. Also, it was moved over to Google Accounts, killing yet another password. Most importantly: spell checking!
Google Reader: Completely new version. This thing is amazing, it really works the way I'd want a blog reader to work. The old Google Reader had really poor performance on Linux, and this one seems to fix it. I only have two issues with the program. First, it does not auto refresh feeds, so I need to remember to hit "r" to refresh things. Also, the server side seems to have less than stellar performance. I'm betting they did such a fantastic job that they got more users than they had server power.
Google Transit: Being a college student, I use public transportation (it's free in the sense that I am forced to pay a flat fee for the entire year). Pittsburgh's public transit does not publish schedules in a usable format. Transit completely fixed this for me.
Groups Beta: Google did a refresh of groups. The UI is much better, and they now have a wiki-like functionality and the ability to upload files (100mb of storage -- that's not too bad). Like Google Reader, the servers aren't quite as fast as they could be. I assume this will be fixed when it's out of beta
Code Search: global grep. No horrible interface like koders or krugle.
Image Labler: This is a version of a game by Luis Von Ahn (a professor here at CMU) that lets people label images. Google needs to do serious work on game play (their images are far too small, likely due to copyright paranoia, and they aren't using taboo words correctly well). However, if you look at the high scores, there are people who have been playing this thing for days. Imagine what would happen if Google were to increase the game play experience and put a link on the home page for one day.

I have to say, this is a pretty amazing array of products.

Constructive Finger Pointing

2006-07-28T20:33:00.000-04:00

Ryan Lortie made a very good post on the waste of power due to timer use. In the past, I have made many similar posts about how memory is wasted. I think these types of blogs provide good insight to the developer community. It's a way to say "wow, this is really a problem". I'd like to see the process automated.

On the Google Intranet, there is a status dashboard. The dashboard is sorted by latency, slowest first. So, if your service is slow, you get highlighted on the home page, with a big red (!) next to your project. I think this is a good incentive to make services fast

I wonder if the same thing can be done for GNOME. We could gather data about which components are sucking and put it in a high profile place (the planet would be a good one). Some metrics are easy to get (modules with the most unreviewed bugs). In time, I think GNOME and distributions should build tools to get other types of data: "what applications are taking up memory", "which apps are segfaulting", "which apps are abusing timers".

Luis von Ahn Talks at Google

2006-07-28T00:40:00.000-04:00

Luis von Ahn, inventor of CAPTCHAs and the ESP Game, gave a talk at Google yesterday. This talk is worth listening to (would I blog it otherwise?). Luis describes how, by using people's spare time, all images on the web could be labeled in months (or even weeks). This talk is non-theory-person friendly (no math). It's also quite funny (Luis' lectures are even better). (direct link if you can't see the embeded version below)

Google Code Hosting

2006-07-27T23:06:00.000-04:00

Hosting Google Code is very interesting. While, at first glance, the site really doesn't compare to Sourceforge, I think it's a really interesting offering:

The Google Code issue tracker is very elegant. The tagging system is much, much smarter than what Bugzilla does.
It will scale. Period. It's interesting to note that some of the biggest investment was on making subversion very scalable (see this interview). Anyone who has ever used Sourceforge knows that the performance of their version control is...less than stellar :-).
Possibly the most interesting thing is the fact that very little infrastructure will be needed to make this service usable; it can just connect to what Google already has. Google Pages, GMail, Google Groups, Blogger and Writely all provide services that in other services would just be one-off hacks. The future of online interaction seems to be combinations of tools that do one thing and do it right into a powerful system. For example, I'm currently trying to convince the people running 15-211 at CMU (the Data Structures course which I TA) to use the combination of Blogger + Google Groups + Google Calendar rather than Blackboard, which is a content management / community system gone wrong. In order to create an integrated experience, I wrote a "portal" (read: 200 line asp.net hack) using the ATOM feeds provided by all three services. It's going to be really interesting to see what a company with so many offerings can do for open source

Yahoo Portal

2006-07-19T02:41:00.000-04:00

I saw that Yahoo released an ajaxish portal today. I tried it, to see if they've improved at all. Let me say, I'm shocked these guys are still around. The site is horrible. First, the home page is filled with ads. I mean the moving, flashing, distracting ads that are so 1999. In addition, the home page has some text ads offering me a range of services I really don't need (Vonage -- no thanks, I don't use the phone that much, domain name registration -- maybe, but does everyone need to see this, "Degrees in as fast as 1 year" -- thanks, I go to a school with reputation, "What’s your credit score 560? 678? 720? - See it free." -- this might as well be in my spam folder).

The featured items on the page are completely irrelevent to most people. In the prime location on the page, I'm offered a contest to "Design Janet Jackson's new album cover". The Yahoo Pulse tells me that the number one "Top Guilty Pleasures Ringtones" is "PYT Pretty Young..." by Michael Jackson.

Well, at least the page has a search box. The focus is on the text box by default (good!), so I can get going right away. Let's give Yahoo a hard search, linq. This is the C# 3.0 Object/Relational mapping. Typical search, not really. But I want a search engine that finds things that are hard to find.

It turns out that Yahoo and Google have about the same search results. However, the difference is in the ads.

Each page has more ads, however for advertisers, the top three are the most important spots, so I'm just going to look at those. The Yahoo ads in positions 1 and 3 offer me some obscure products that happen to be named "linq". Yahoo ad 2 links to www.restaurant.com with no connection what so ever to linq. Compare this to the Google ads, all of which might be relevent to somebody looking at O/R mapping in .NET. Let's just say Google is getting lots more revenue from its ads.

Ok, let's give Yahoo a break. I'll try an easy query "restaurant". Yahoo highlights restaurant results in Pittsburgh (right now, I'm in CA). Now, I know I've used Yahoo's farechase to find flights from PIT to SFO, but my IP address should very clearly tell Yahoo where I am. All of Yahoo's ads are for restaurant supplies Now, Google doesn't try to highlight local restaurants (to do that I have to say "restaurant near mountain view ca"), however the ads are geo-targeted, giving local restaurants (not restaurant suppliers).

Well, I don't think I'll be changing my home page any time soon. There are some things I did like about Yahoo's design (I really like that you can change from Web to Image search without the page being refreshed. Google should totally copy that idea). However, it's pretty clear why Google has so many users.

Today in performance

2006-07-04T21:38:00.000-04:00

I started off today by using massif and the traditional memcheck to see where memory was allocated in the libgnomeui stack

We use libgnutls to handle ssl in gnome-vfs. This program mallocs 65 kb of memory in the intializer (which is called from gnome-vfs's initializer). I sent off an email to the address their website told me to use for bugs (no bugzilla!). If you are interested in fixing this on the gnutls side, the code to look at is gnutls_global_init, specifically the two calls to asn1_array2tree. In the mean time, I think we should fix this in GNOME by lazily initializing the tls library. I think this is a pretty rare use case. On my (basically empty) desktop, 18 processes are using gnome-vfs. That makes 1.1 MB (probably more, countin malloc overhead).
Noticed lots of allocations from inside glibc when calling setlocale (which the gnome option parser does). Turns out there is a glibc cache for this stuff, but Ubuntu wasn't packaging it. Filed a bug. I have 40 processes using the cache right now (even bash uses it!). Not using the cache costs about 70kb. That's 2.7 mb.

I then went on to look a bit at gedit, which I noticed was taking up a pretty high amount of memory

First sign of trouble: gedit loads python. Why? By default a plugin called "modelines" which describes itself as "Emacs, Kate and Vim-style modelines support for gedit". I'm not sure exactly what that does, or how I'd use it. Disabling just that plugin gives me back 3.2 mb of ram. It also made gedit feel faster to start up. Filed a bug suggesting that it either be disabled or written in C.

It looks like python+gtk could use some memory optimization. For startup, a hello world in Python has 4 mb of private dirty rss. Compare this to Mono and Gtk# which takes only 2.7 mb. Granted, even Mono is large compared to 608 kb for a C based GTK app. I'll see what I can do about that some weekend :-).

Ubuntu's launchpad-integration library was taking up quite a bit of memory by allocating pixbufs. strace -eopen gave the issue away:

open("/usr/share/pixmaps/lpi-help.png", O_RDONLY|O_LARGEFILE) = 17
open("/usr/share/pixmaps/lpi-translate.png", O_RDONLY|O_LARGEFILE) = 17
open("/usr/share/pixmaps/lpi-help.png", O_RDONLY|O_LARGEFILE) = 17
open("/usr/share/pixmaps/lpi-translate.png", O_RDONLY|O_LARGEFILE) = 17
... (78 lines of this)

Whoops :-). Filed a bug. Not sure how much this saves, as it's not easy to count how many times this code is used.

So, that's about 7 mb of memory from all these issues (and my estimates are fairly conservative -- I'm rounding things down, not counting malloc overhead, and looking at my desktop with just xchat, gaim, firefox, gedit, and a few terminals), I'd actually expect the total effects of these to be 8-10 mb. Even with 1 gb of ram, that's pretty large.

gnome cups icon leak

2006-07-03T16:18:00.000-04:00

The printer status icon (gnome-cups-icon) leaks quite a bit. There is a Debian and a GNOME bug. It looks like there has been no maintainer attention to the bug since it was filed. Now that there's a patch, it'd be great to see some action. It looks like this is a fairly visible leak.

Why does libgnomeui cost so much

2006-07-02T18:07:00.000-04:00

So, after measuring the benefit of removing libgnomeui from a program, I thought I might dig deeper into the cause of the bloat. I first made three hello world style applications: one used plain GTK, another used GTK but also initialized GNOME VFS, the last used libgnomeui (which also uses vfs). Each of these three programs loads a superset of the libraries of those before it. I used smaps to gather data about the heap space allocated (used by malloc) and the writable mappings due to shared libraries.

Some observations to make here:

Malloced memory causes the most trouble at the gtk level. However, the gnome vfs and libgnomeui are still responsible for quite a bit of mallocing
libgnomevfs is the worst offender with respect to loading libraries.
libgnomevfs is a much larger jump in memory than libgnomeui

I then dug further into what libraries were being loaded by vfs and gnomeui. To get useful data here, I excluded the libraries loaded by gtk from consideration when looking at vfs and similarly excluded libraries loaded by vfs when looking at gnomeui.

Bonobo, ORBit...ugh
libgnutls, libxml2, and libgcrypt have quite a bit of writable memory. If they could be cut to 4 kb each, we'd save 50kb for each process with gnomevfs.
The "Other" category has all the 4 kb libs. A few worth special mention: avahi loads three .so files. First, having avahi here seems a bit silly; second, three libraries. Also, libpopt is used, isn't there something in glib for this now?

Maybe all those sound related libs should be dynamically loaded. Not many apps use sound!

Investigation to do

Look at the malloced memory. Valgrind is a good tool here
Look at the size of the writable memory in libraries mentioned here

Kill libgnomeui

2006-07-01T20:10:00.000-04:00

libgnomeui would be better named "libkitchensink". It brings in all kinds of libraries from avahi to zlib. How much effect would removing this dependency have on memory? I decided to try out on gnome-volume-manager (which handles volumes as in mounts, not as in sound). Hackishly, I commented out the session management stuff that requires libgnomeui. The results were pretty good.

That's 800kb of memory (I'm using the private dirty rss number, aka "the number that matters"). There are 17 processes on my desktop using libgnomeui right now. If we can remove the dependency from all of those, it would get us 13 MB of savings. In addition to the memory savings, this would likely speed startup speed quite a bit. FYI, the list of processes using libgnomeui right now is:

/usr/bin/gnome-session
/usr/lib/control-center/gnome-settings-daemon
/usr/bin/gnome-panel
/usr/bin/nautilus
/usr/bin/update-notifier
/usr/bin/gnome-volume-manager
/usr/bin/gnome-cups-icon
/usr/bin/gnome-power-manager
/usr/lib/gnome-applets/trashapplet
/usr/lib/gnome-panel/clock-applet
/usr/lib/gnome-applets/mixer_applet2
/usr/bin/gnome-terminal
/usr/lib/firefox/firefox-bin
/usr/bin/eog
/usr/bin/evolution-2.6
/usr/lib/evolution/2.6/evolution-exchange-storage
/usr/lib/evolution/2.6/evolution-alarm-notify

I'm quite sure that we can kill the library from many of those. If one looks for GNOME VFS (which is responsible for quite a bit of the bloat), there are even more processes that could use dependency pruning.

notification-daemon

2006-06-29T12:20:00.000-04:00

notification-daemon displays those "you've got 10 minutes of battery left" dialogs. To launch it, you send a dbus signal. A file in /usr/share/dbus-1/services launches the servicce when the dbus interface is called.

An interesting thing I noticed today: if I kill the notification-daemon process, I can still get messages. The process just gets relaunched by dbus. Why the hell doesn't the process quit when no notifications are active? This would save 3.1 MB of memory on my system.

Filed here.

Google Checkout

2006-06-29T09:53:00.000-04:00

Google Checkout was released today. In the great slashdot tradition, the story is sold as "Google is releasing an X killer" where X is a product that does something similar but has a totally different goal. (Google Spreadsheets the "excel" killer, etc).

Two things about Google checkout are very interesting to me. First, the ability for Google to provide the user with some sort of confidence in the checkout process. I never really liked Froogle all that much because it'd point you at some random store that just happened to have a website.

The second thing I like is that Checkout offers an anonymous email service. The ability to shut off email from a seller if they get out of hand is very, very nice. (as I understand it, it also offers the ability to forward email for the inevitable email address change. However, it seems the main functionality is being anonymous).

Of course, there's always a down side to things. I'm quite sure this will cause an increase in phishing emails for Google accounts. With that said, it looks like Google is using smart measures to make sure a stolen password won't be of much use. Also, I'd think that gmail users would be especially safe from phishing (when GMail team gets a phishing report, I'd assume they can retroactively filter it).

The checkout support site also has some (basic) information on what the anti-fraud team does. I can assure you, the process is much more complex than that site makes it sound :-).

Powered by Google Maps

2006-06-17T01:25:00.000-04:00

While Google can't find you a date, with the combined power of Maps API and somebody who has way too much time on his hands, you can tell the world what happened (and where it happened) after you got one.

onmousedown and performance

2006-06-16T01:41:00.000-04:00

While checking my email on my coporate GMail account today, I noticed that when I clicked on a button in GMail (eg, Inbox, or on a message), it starts to open when you press the button down, rather than when you release it to make the full click. This is not the typical behavior of a site (try it on any other hyperlink).

After pondering for a while, I realized that this must be a performance thing. It must take 50-100ms for one to complete a click. However, pinging google.com from here (home, on a wireless connection) takes about 70ms. That head start by capturing onmousedown must be enough to hide most of the delay in fetching stuff.

With a bit of further investigation, I found that Google Search uses the same thing. If you look at the html for a typical query, you will see onmousedown="return rwt(.... rwt appears to be a function that sends a request to google.com/url with a query string that tells what result was clicked. This would make sense in collecting stuff about are the best results really on the top position. It's genius that they slip this tracking in the onmousedown so that it does not affect user performance.

Bad situation #153

2006-06-12T15:50:00.000-04:00

You print out the design for something you need to use. The first line is:
Status: CURRENT (as of November 19, 2003)

It's time to start grepping the source code for what I need.

Please don't me-too on bugs I blog

2006-05-22T13:32:00.000-04:00

On one of the Launchpad bugs I blogged, there have been a few me-too posts saying Yeah, this problem sucks. Let's fix it. Please do not do this. When I blog about a bug, I have two goals. First, it allows people reading my blog to get an idea of what issues are being looked into in the performance front. If you are interested in our progress, you should feel free to subscribe to the bugs. Subscribing can be viewed as a vote for the bug. Second, I'd like to highlight some of the easy wins to the developer community. Commenting on a bug saying I wish you would fix this helps nobody, and increases the time people have to spend on bugzilla. Please don't do it, or else I'll have to stop blogging bugs.

Performance: The Good, The Bad, And The Ugly

2006-05-21T16:22:00.000-04:00

The Good

The latest Dapper betas are starting up GNOME with less than 95 MB of ram. This is really impressive. Everyone involved in this should feel really good about it.
I think we're making good progress in terms of startup memory usage in general. In the next round of distros, I'm willing to bet we can bring the GNOME startup cost to about 85 MB. This will result in startup time reductions for everyone (even those with 1 GB of ram) and will be very important for low-memory users

The Bad

My box wastes 3.4 mb of private dirty ram to load hpssd, some sort of HP printing thing. I don't have a HP printer. Even if I did, why does 3.4 mb of stuff need to be loaded? This piece of software simply needs fixing. There's already a bug on this in launchpad.
Evolution sees it fit to launch evolution-exchange-storage just because the Exchange plugin is installed. This wasts 1.6 mb of private dirty ram. I personally think distributions should remove evolution-exchange from the default install set until this is fixed. Exchange users are likely using managed distros. Those people can install the plugin along with their other configurations. I filed a bug for Ubuntu to remove this from the default install. I also filed a Evolution bug.
The way Ubuntu uses gettext to translate gnome-panel items caused 1.2 MB of memory to be used

The Ugly

We load way too many processes at startup. nm-applet, gnome-volume-manager, gnome-power-manager, etc. All of these are loading must of the same stuff in their address space. I think we need to have some shared infrastructure for desktop plugins that listen for some sort of event and then take action on it. These are all small, simple tasks that should be in one process.
Firefox, Evolution, and OpenOffice are still taking much more memory than they should. We may be reaching the point of diminishing returns in desktop startup memory. We will need to turn our focus to these apps.

Life as a Noogler

2006-05-20T03:03:00.000-04:00

It's the end of my first week at Google. It was a fairly mundane week. The first day I set a password, got a Google badge, and filled out forms (they have a very nice automated system that made filling out 16 forms a quick job). The food is, simply put, fantastic. A typical Google lunch would be a $20 dinner. The menu at Charlies, Google's primary eating establishment, has a wide varity of selections. The snacks are just as good. It's like I'm living in Whole Foods.

There are a few things I'm getting used to at Google. It's really different than the world I'm used to. The oddest thing is how hush hush everything is. Every meeting starts out with "this is confidential". Sure, at Novell I had to deal with some things that were under NDA. In Google, you presume all knowledge is under NDA by default. Second, everyone at Google is new, or so it seems. When a social event is done, it seems like a common exercise is for people to raise their hand if they are new. A large number of people do this. The introductory training sessions are huge. Google is growing at a rapid rate, it's really exciting.

One of the most exciting parts of being at Google is the fun stuff to explore. Interns have access to almost all of the Google code base (interns fall into a bucket called nonconfs who have a few restrictions, such as not being able to see the pagerank code). It's hard to resist the urge to explore code when there is work to be done.

In other news: GStreamer was loading too many plugins in each process. This caused a few extra MB of private dirty memory for gstreamer using programs, like the settings daemon and mixer_applet2. This should be fixed now.

ps noogler == new googler

Google Trends

2006-05-12T14:17:00.000-04:00

Google Trends is a really cool service. In case you don't read Slashdot, it gives you stats on who searches for what. Some are rather interesting, for example, you can find out what the popular Linux distros are in different parts of the world.

suse fedora ubuntu debian

Around the World

In the US

In Germany

Google Trends also has great tastes in education.

Carnegie Mellon University Massachusetts Institute of Technology

Track down your first leak!

2006-05-09T15:42:00.000-04:00

Now that gnome-system-monitor gives useful information, I've been keeping it open quite a while. There is pretty clearly a slow memory leak. The heap grows by just keeping it open (i've been having it in the process view). You need it open over a period of a few hours to notice the leak. I first saw it after leaving it on over night.

Want an easy way to get your hands dirty with performance? This is your chance. I've filed the bug as #341175. Here is the plan of action:

Reproduce the bug, make sure you can see it. I'm using GNOME 2.14, as it is packaged on Dapper.
Run G-S-M under valgrind. I like to use the following flags valgrind --num-callers=20 --leak-check=yes --show-reachable=yes --leak-resolution=high gnome-system-monitor. This will generate a large dump file, because it showes stuff that's still reachable. However, this will help you if gsm retains pointers to memory, but just doesn't use it.
Figure out who's to blame
Patch it

If you complete any of these steps, please update your progress in the bug report. Again, this is a great chance for somebody new to performance work to get involved. If you need help, go to #performance on IRC, and one of the performance hackers will help you.

Talking of performance masters, Ubuntu users should thank Sebastien Bacher. The fair seb128 checked in a patch that puts many of the gnome-panel applets in process. This saves a good amount of ram. Thanks Sebastien!

USB Wireless Help

2006-05-09T15:36:00.000-04:00

If you have experience using a USB wireless adapter on Linux, I'd really appreciate an email (bmaurer+usbwifi@andrew.cmu.edu). I've been having quite a bit of trouble finding something supported. Many thanks!

Thanks to those who responded. Responses I got, by chipset: prism, atmel (reported to require some hacking to get working), Ralink rt2570. One person recommened SWEEX Usb WLAN LC100010, saying it worked out of the box. Again, thanks for the quick help!

Breaking news: g-s-m now gives useful information

2006-05-08T20:26:00.000-04:00

Tired of guessing what 20 MB of RSS really means? Want numbers that give you statistics that aren't lies. Wait no longer. With a simple patch gnome-system-monitor version 2.14.2 gives useful information when combined with a modern kernel (in FC5, Ubuntu Dapper, or SUSE 10.1).

This new statistic is the Writable Memory column in gnome-system-monitor. You may have to modify your preferences to expose this. This column gives you the private dirty RSS, the memory statistic which I've talked about in previous posts. This is the amount of memory that is private to your process, modified from the on disk version, and loaded into memory. The number is a very good indication of how much memory you are using.

Note how the Writable Memory column is less than the traditionally used RSS. This is becaused shared rss is not taken in to account.

I'd like to propose that we make One True Statistic for g-s-m: writable memory + X memory. This is an very accurate accounting of memory usage. I think it's as good as we can get without further kernel patches.

Fighting Daemons

2006-04-09T12:03:00.000-04:00

One of the things I love about GNOME and Linux in general is the philosophy of "do one thing, and do it right". However, we may have taken this to an extreme in the GNOME community. The GNOME desktop has seperate daemons for a plethora of simple tasks. nm-applet sits around and waits for the network connection status to change. Great, I love nm-applet. But does this task warrent 2.7 MB of memory? According to my smem script, this is the amount of private dirty rss the task takes.

To initialize the GTK+ framework (among other frameworks), one must allocate a given amount of memory on the heap. Depending on what parts of the stack (dbus, libgnomeui, etc) one loads, this ranges from 1-3 MB. While it's important to work to fix this (eg, by mmaping things), there's only so much we can do.

I believe it would be beneficial to have a host process for daemons like this. The system would need to be set up in such a way so that mini-daemons could be put into a different process via configuration (eg, for debugging).

One of the types daemons on the desktop is panel applets. We have a process to display the clock, the volume switcher, etc. The panel already has a framework for doing these in process. What would be the benefit of using this? To find out, I put two applets in process: the wnck-applet which handles the workspace switcher and task list and the notification-area-applet, which handles the notification tray.

I actually already had the patch for this. openSUSE already uses a similar patch thanks to Federico. I decided to modify the patch so that it would not put clock-applet in process. Some people have complained that because this links to evo, it might be at risk for crashing. Fine, whatever. Let's start with some low hanging fruit.

Here are the results for private dirty rss, before and after the patch.

Process	Before	After
gnome-panel	4008 kb	4248 kb
notification-area-applet	1368 kb	--
wnck-applet	3056 kb	--
TOTAL	8432 kb	4248 kb

This is over 4mb! Just for putting two things in process. There are three other applets on my Dapper computer that could benefit just as easily: trash-applet (trivial), mixer applet (see below), clock applet (links to evo stuff. maybe?). I hope other distros follow the led of openSUSE in this area.

One thing to look at: the mixer applet loads every single part of gstreamer. This causes extra memory usage (gstreamer plugins badly need constification), as well as extra spinning of the disk. Can this be fixed?

Google

2006-04-08T13:48:00.000-04:00

I will be interning at Google this summer in the AdWords anti-fraud team. This is a really exciting opportunity for me.

I'd like to publicly thank my friends and colleagues on the Mono project for the fantastic learning experience I've had over the past three years. There are a few people I'd like to give an extra-special thanks:

Sebastien, for guiding me through my first project, BigInteger.
Atsushi, for guidance on the project I'm probably most proud of, the XSLT engine.
Paolo, for code reviews that have begun to teach me the meaning of "good style" (and I admit, I'm still learning).
Miguel, for believing in me and being a great mentor/friend/boss.

I'll still work with Mono on the side and stay in touch via IRC and email.

If you are a college (or high school student) reading this, I would like to give you one piece of advice. Get involved in an open source project. It will be the best choice of your life. Even the world's best computer science schools are very bad at teaching you what you really need to know to get work done. CS classes teach theory, not how to write good code. Hacking on open source software is the best way to be a smart programmer. Open source projects are more than happy to take on a dedicated hacker, even one who makes mistakes at first. Hacking will be the best decision you ever made. Your chances of getting an internship are greatly increased by working on OSS.

As a side note: for those of you who missed my previous blog because pgo wasn't picking up my feed, I'm going to GUADEC. Be prepared to kill bloat.

(I promise performance blogs are coming soon. Really)

Newslets

2006-04-06T19:50:00.000-04:00

I'm going to GUADEC, now that I am being sponsored. Be prepared to kill bloat with the Ben, Federico, Behdad team. If you're interested in memory reduction, it'd be great to have you.
With leadership from Daniel Holbach, Ubuntu will be using the icon cache. Yay.
I promise for some more juicy memory reduction content soon, after I finish 15-251 (Discrete Math) homework.

More Icon Cache

2006-04-02T22:53:00.000-04:00

It's too bad that we are at a standstill as to using the GTK Icon Cache in Ubuntu/Debian. Clearly, both Fedora and SUSE have implemented the standards defined policy and have (to my knowledge) not encountered major issues.

While the impressive number of over 300 packages quoted on the Ubuntu bug seems like a very hard task, distributed across many contributers, I can't imagine this being a blocking issue. As for 3rd party apps: sure, could cause a third party app to break. But the same app will be broken on any other issue.

Even if the Debian folks absolutely do not want to risk breaking something, how about at least using the shared memory aspect of the cache? You can stat every directory in /usr/share/icons to make sure the cache is valid. But if it is, you'll save 300kb per process by using the cache.

Anyways, it looks like the spec is staying as is. The folks upstream have given (IMHO) a well reasoned argument that the spec is implementable and reasonable.

Make sure to use the Icon Cache

2006-03-31T12:49:00.000-05:00

It's sad when people take great efforts to optimize the memory usage of a program, only to have the optimization not used. It seems like, due to a packaging bug, Ubuntu isn't taking advantage of GTK's icon cache, wasting 300 kb per process.

Not sure what we can do to make sure every distro takes the actions necessary to get the best performance out of GNOME, I guess there's always the process of filing bugs.

Zenity Memory Usage: Valgrind

2006-03-30T14:38:00.000-05:00

So, on the latest Dapper beta, I tried running valgrind on an instance of Zenity, a fairly good example of a minimal gtk program. I noticed that stuff was getting allocated for the icon data:

==24632== 74,477 bytes in 2,864 blocks are still reachable in loss record 4,829 of 4,830
==24632==    at 0x401C422: malloc (vg_replace_malloc.c:149)
==24632==    by 0x479FF36: g_malloc (in /usr/lib/libglib-2.0.so.0.1000.1)
==24632==    by 0x47AFC65: g_strdup (in /usr/lib/libglib-2.0.so.0.1000.1)
==24632==    by 0x42BAD04: ??? (gtkicontheme.c:2161)
==24632==    by 0x42BAF11: ??? (gtkicontheme.c:1057)
==24632==    by 0x42BBC5F: gtk_icon_theme_lookup_icon (gtkicontheme.c:1244)
==24632==    by 0x42BC108: gtk_icon_theme_load_icon (gtkicontheme.c:1388)
==24632==    by 0x42B74C1: gtk_icon_set_render_icon (gtkiconfactory.c:1748)
==24632==    by 0x43D0CAB: gtk_widget_render_icon (gtkwidget.c:5337)

There were other stack traces here, accounting for over 200kb of memory. I tried regenerating my cache, this had no effect. Have to see what is going on. Also, this stack trace was very curious:

==24632== 337,656 bytes in 94 blocks are still reachable in loss record 4,830 of 4,830
==24632==    at 0x401C422: malloc (vg_replace_malloc.c:149)
==24632==    by 0x494FC0C: (within /usr/lib/libfreetype.so.6.3.8)
==24632==    by 0x41B0E9A: (within /usr/lib/libpangoft2-1.0.so.0.1200.0)
==24632==    by 0x41B6974: (within /usr/lib/libpangoft2-1.0.so.0.1200.0)
==24632==    by 0x41B237A: (within /usr/lib/libpangoft2-1.0.so.0.1200.0)
==24632==    by 0x41B4DA1: (within /usr/lib/libpangoft2-1.0.so.0.1200.0)
==24632==    by 0x41B02D1: pango_ot_info_get_gpos (in /usr/lib/libpangoft2-1.0.so.0.1200.0)
==24632==    by 0x41B0357: (within /usr/lib/libpangoft2-1.0.so.0.1200.0)
==24632==    by 0x41B0407: pango_ot_info_find_script (in /usr/lib/libpangoft2-1.0.so.0.1200.0)
==24632==    by 0x4C162E9: (within /usr/lib/pango/1.5.0/modules/pango-basic-fc.so)
==24632==    by 0x45E4D12: (within /usr/lib/libpango-1.0.so.0.1200.0)
==24632==    by 0x45F3FB3: pango_shape (in /usr/lib/libpango-1.0.so.0.1200.0)
==24632==    by 0x45E7BCE: (within /usr/lib/libpango-1.0.so.0.1200.0)
==24632==    by 0x45EAD1A: (within /usr/lib/libpango-1.0.so.0.1200.0)
==24632==    by 0x45EB274: (within /usr/lib/libpango-1.0.so.0.1200.0)
==24632==    by 0x45EBBCB: (within /usr/lib/libpango-1.0.so.0.1200.0)
==24632==    by 0x42DA876: ??? (gtklabel.c:2027)

I wonder exactly what this is that needs 300 kb of memory.

libaudiofile patch

2006-03-22T21:31:00.000-05:00

Jason Allen commented on my last blog with a patch to fix libaudiofile. This simple patch just adds const to lots of data tables. It trims the 92 kb of dirty private rss down to 8 kb, saving just under 2 mb desktop wide! Jason: this patch is great. Let's get it upstream, and also try to get the next round of distros (suse 10.1, dapper, fc5) to include this.

There are quite a few other libraries that are used by almost every GNOME process that could benefit from such constification. Some I saw from gnome-terminal:

      48 kb        0 kb       48 kb   /usr/lib/libORBit-2.so.0.1.0
      40 kb        0 kb       40 kb   /usr/lib/libbonobo-2.so.0.0.0
      36 kb        0 kb       36 kb   /usr/lib/libgtk-x11-2.0.so.0.800.16
      36 kb        0 kb       28 kb   /usr/lib/libxml2.so.2.6.23
      24 kb        0 kb       24 kb   /usr/lib/libgnutls.so.12.3.6
      20 kb        0 kb       20 kb   /usr/lib/libasound.so.2.0.0
      20 kb        0 kb       20 kb   /usr/lib/libfontconfig.so.1.0.4
      20 kb        0 kb       20 kb   /usr/lib/libgnomevfs-2.so.0.1400.0
      20 kb        0 kb       16 kb   /usr/lib/libgcrypt.so.11.2.1
      16 kb        0 kb       16 kb   /usr/lib/libX11.so.6.2.0
      16 kb        0 kb       16 kb   /usr/lib/libgnomeui-2.so.0.1400.0

Fixing one of these libraries will have the benefit multiplied by about 20.

We should also consider is reducing the number of processes on the desktop. For example, clock-applet takes up 2.7 MB of private dirty rss. 1.7 MB of this is the heap and stack, the other MB is the .data section of .so files. For the most part, these are constant costs we are going to experience with any process. Reducing the number of processes will reduce this problem.

Memory Usage with smaps

2006-03-21T20:44:00.000-05:00

As most developers should know by now, the memory statistics given on Linux are mostly meaningless. We have the vmsize, which counts the total address space used by a process. However, this is not accurate because it counts pages that are not mapped in to memory. We also have rss, which measures pages mapped into memory. However, it multi-counts shared pages: every process gets X kb of rss due to libgtk. However, the majority of the pages in libgtk are shared across the processes.

What we really care about is the private rss, the amount of pages our process maps in to memory that are only used by our process. We'd also like to know the rss per mapping so that we can point-fingers/find-where-to-fix-the-bug.

Up until this point, such statistics have been hard to come by. No longer! The 2.6.16 kernel adds support for smaps, per-mapping data, including data on each mapping's rss usage. This data lives in /proc/$pid/smaps. However, the format of the smaps file is hard to digest. I've written a quick perl script which parses this into something more useful. It uses the Linux::Smaps module on CPAN.

An example of the data generated by this script:

VMSIZE:      41132 kb
RSS:         23052 kb total
         9212 kb shared
            0 kb private clean
        13840 kb private dirty
PRIVATE MAPPINGS
vmsize   rss clean   rss dirty   file
12768 kb        0 kb    12616 kb   [heap]
196 kb        0 kb      196 kb
120 kb        0 kb       92 kb   /usr/lib/libaudiofile.so.0.0.2
132 kb        0 kb       80 kb
 80 kb        0 kb       60 kb   [stack]
 48 kb        0 kb       48 kb   /usr/lib/libORBit-2.so.0.1.0
 40 kb        0 kb       40 kb   /usr/lib/libbonobo-2.so.0.0.0
 36 kb        0 kb       36 kb   /usr/lib/libgtk-x11-2.0.so.0.800.16
...
SHARED MAPPINGS
vmsize   rss clean   rss dirty   file
2848 kb     1596 kb        0 kb   /usr/lib/libgtk-x11-2.0.so.0.800.16
1172 kb      624 kb        0 kb   /lib/tls/i686/cmov/libc-2.3.6.so
488 kb      400 kb        0 kb   /usr/lib/libgdk-x11-2.0.so.0.800.16
900 kb      396 kb        0 kb   /usr/lib/libX11.so.6.2.0
524 kb      360 kb        0 kb   /usr/lib/libglib-2.0.so.0.1000.1

The vmsize and total rss size are the statistics that everyone is used to. The rss size is split into private and shared. The private rss is what could be best called the process' memory usage.

Below this, we give the per-mapping statistics for private mappings. Most of these are either from the heap (eg, malloc'd data), or writable mappings in .so files (from the .data section). This output is especially helpful for diagnosing the second kind. Following, we give the same data for shared mappings (most of which are .so files, the executable code, etc).

Call to action: I would love to see the following done:

Check out some of the libraries with large writable segments. An extreme example of this is libaudiofile. This library has 92 kb of dirty, private rss (isn't that naughty!). To make matters worse, the library is used by 22 processes on my GNOME 2.14 desktop. This is about 2 MB of memory! Let's figure out why this is happening and make the data const. Also, it might be wise to see if we could reduce the number of programs using this library. We should try to find any other instances of this.
Let's get some smaps based data in gnome-system-monitor, and possibly more low level tools as well.
We should look at tools like exmap to get per-page level rss into. This is useful for finding out things like what pages does evolution use from libgtk and why. We can use this tool to figure out what we can do for low memory users: we can simulate high levels of swapping by allocating memory in a dummy process. We should then see what pages must be loaded from disk to use the desktop, evolution, etc.
It'd be great to set a community goal for 2.16. We will reduce the private rss used by all GNOME processes in setup X by Y MB. We should also take statistics from 2.14 to make sure that there are no memory usage regressions.

In other performance related news, somebody has finally gotten good statistics on Firefox's memory usage. It looks like Mozilla is leaking pixmaps when browsing with tabs. I think there are many people who would be made much happier if this could be fixed. This is really great data gathering, and I'd like to see more of it.

Web desktop?

2005-11-28T02:03:00.000-05:00

Miguel, your ideas aren't without merit. However, I am a bit scared of the web desktop. First, this would involve a substantial security risk, just by exposing new applications to external threats. Probably not an issue at home for you, since you are a home user with a firewall. But here at the university, opening up a port means opening it to the world. Needless to say, I'd hope that any such service was off by default, and had a good audit. Second, is it really necessary for each application to provide the functionality from scratch? Windos users have had SMB/CIFS since forever. If I want to share files with my family, I tell them to go to \\ben\photos, and they'll see the photos. In your case they go to http://ben:123/photos. Of course, the http user will get a spiffy UI. But what are the advantages to the SMB method:

One central security provider (the ACLs on the files). One program to audit
No work required for the application programmer
The files can be accessed even if f-spot or whatever isn't open

What about a combination of the two: we use Apache (a very well audited server) to serve up webdav based file sharing. Windows, Linux and Macs should be able to mount webdav shares. WebDAV could become the Linux SMB. However, users could also use a custom browser based view with search/rich ui. With your plan, it seems like every application would be reinventing the wheel.

Pornography And CMU

2005-11-10T13:52:00.000-05:00

Interesting email in my in box this morning. The SCS Frosh Advisor emailed the list that a student asked for an IC point [1] to be offered for watching an adult movie that is being shown at CMU.

Historically, it has been found that if CMU published in the schedule of movies that it was shoing an adult film, some local media would make a fuss about it. So, a semi-secret code was adopted that adult films would be listed TBA. I say semi-secret because Google knows what this means. My advisor decided not to offer an IC point (even though one of the tasks had been "watch a movie at cmu") for the TBA movies, reasoning that he should try to avoid "CMU Advisor Encourgages Porno" in the local tabloid^Wnewspaper (of course by blogging that I've somewhat circumvented this ;-).

One piece of advice Rich gave was that when he was a student at CMU he attended a showing of _Deep Throat_ and found that the effect of watching porn was reduced by watching it with a large group of students in a large auditorium. Sounds logcial.

[1] For background the IC is the SCS frosh imigration course. In order to pass this course we must attend almost all of the (sometimes boring) weekly guest lectures. We must also earn "IC" points which are basically proof that we did things other than sit in front of a computer. The point list is here

EDIT: at Rich's request I've removed the original email

Numbers

2005-09-29T00:55:00.000-04:00

Pretty good joke I heard today:

President Bush was at a meeting yesterday when one of his advisors told him that a Brazilian soldier had been killed in Iraq.

"OH NO!" shouted Bush, "that's terrible!"

A silence fell over the room while everyone looked at Bush.

He looked back up the advisor with tears in his eyes and said "Just how many is a Brazilian!?"

The President would not fare well at CMU

The life of CMU CS Frosh, in pictures

2005-09-26T02:01:00.000-04:00

This, and more on the SCS Freshman Photo Web Site, being run on the desktop computer here in my dorm.

RE: Should I use Gnome#?

2005-09-23T11:20:00.000-04:00

jluke, you have fallen into the all too common trap of relying on RSS statistics as a measure of memory usage. RSS means "how many pages of memory did this process use". This number includes shared pages. Now, I think it's a reasonable assumption that alot of pages from libgnomeui.so etc are paged into the system without the Mono application in question. What you really want to count is how many private pages get into memory. This is much harder to measure, in fact, we don't have the tools to really do this correctly.

That being said, there are other reasons not to use Gnome#, one of which being that better versions of the stuff in there are being moved to Gtk#.

If you are thinking about measuring the amount of ram a process uses, please, please, please be careful about what numbers you look at. It's really easy to come up with nutty conclusions.

Linux for College Students

2005-08-28T02:15:00.000-04:00

It is pretty interesting how many CMU students want to try out linux but don't know how. And these are not just male CS students -- a diverse range of people is interested in what else is out there. Firefox has huge exposure at CMU and on other college campuses. People know about Linux but don't know how to take the plunge. I think it is important that we try to incubate new Linux users at universities like CMU. These are our future engineers, scientists, and programmers.

So, I think the best way to start thinking about this is "what do students do with their computers?" With a corporate desktop (like NLD) this part of the game is pretty easy. Employees have well defined tasks. College students are a much more interesting crowd. I don't think we will be able to replicate 100% the programs that students are used to. But let's take a look at what is important:

Being able to play every video and music format on Earth.
P2P sharing (i2hub!)
Using Flash
Fully functional java environment (eclipse+tools+your choice of gcj or sun java)
Being able to read every pdf thrown at them (that means acroread -- I love evince but there are some documents it does not want to read).
0-hassle integration with their campus network (at CMU, afs should be mounted)
Allow easy installation of university licensed software (mathematica!)
iPods must work with no hassle.
All wireless cards must work (I had to go through some hoops to get my Dell laptop's wireless to work. Not cool).

The most important part is taking a stock distro and making it do the tasks I listed above extremely easily. We can't expect people to go through 100 hoops just to play a DVD. There are some obvious legal issues here. But given that we college students have found ways to host terrabytes of copyrighted music and video, I don't see why it should be such a challenge for us to host a small amount of software that may have whatever issues.

Once this step is done, we would need to consider how to get Linux out to users. I think this has two aspects. First we need to have "Linux Heros" who can help people out. facebook would be a great place to start this. The second aspect is making it easy to actually install Linux. On a campus network, bandwidth is virtually free (at least within the univ. and other internet2 campuses). Therefore, the media should come from the campus network. I think a pxeboot system would be very powerful: with the help of a person familiar with how to use the BIOS, Linux can be installed with no physical media. Also, "kickstart" disks could be distributed that would boot to the pxe system for people with network cards that don't support pxe or who don't know how to use the bios.

I guess the way to start making this work would be to get a list of rpms that can be installed to make my above task list work. If packages don't exist, we need to create them. Where possible, we should prefer open source, patent-free stuff, but where that does not exist/does not have the functionality students need/etc, other solutions are needed.

Late breaking ideas

What if we make a Windows program that modifies the MBR so that on the next boot, it will go to the pxe server. This allows people to use pxe without touching the bios and without needing any physical media
Presentations / Demos of Linux
Form a community. Do some non-geeky stuff. Ice cream social for Linux. Could be integrated with presentations (hook them with ice cream, get them to watch the demo of linux)
Give "Linux Heros" free t-shirts. If we have enough heros, it won't be hard to find a person wearing their tshirt on any given day. These people can answer questions.

Later Breaking:

See GRUB docs for ideas about booting from the network. So we give the user a grub config file with the pxe server specified
Install grub on windows without touching the MBR. If I understand this correctly, it would mean a dual stage boot: first it goes into the NTLDR menu then the grub menu. But, it sounds a bit less risky.

Laterer Breaking

A guide to installing Linux with no media
Going with the community, how about an irc hangout for linux users at university?

At CMU

2005-08-27T13:51:00.000-04:00

Am at the CMU campus:

In the center is Hamerschlag Hall. The large tower on the right is Pitt's Cathedral of Learning. The ugly looking slab on the right is Wean Hall, the CS building.

Abstract art at Carnegie Museum of Art (cmoa):

Still CMOA, but now much more fun. Who said adults can't enjoy the children's section.

Off to college

2005-08-20T00:47:00.000-04:00

On Sunday, I'll be going off to college:

One week of orientation (the schedule is literally 40 pages long. Hopefully, there is a list of important things :-), and then classes. I'll have to start programming in Java. Given that I convinced the CS department to let me into a fairly advanced class, it would probably be a Good Thing to know how to write a "hello world" in java by the first day of class. How long will it take me to get used to javaCase? And then how long before I leak javaCase into CSharpCase? I wonder if I could get away with using Mainsoft's stuff and claiming that my c# code is actually Java.

Msdn Browser

2005-08-18T00:50:00.000-04:00

Browse msdn without an insane treeview and without an insane browser. Source is here. It's only 220 lines, you can read it really quickly!

Left to do:

Integrate into monodoc
Make it handle T:System.String style links in monodoc (would allow it to replace the default class ref).
Handle clicking links inside the msdn content area
Greasemonkey-like modifications of MSDN's content

Remove syntax for VB, etc.
Remove the msdn footer

Use a cache for the xml

Would be cool to use mozilla's cache here. That means I can avoid writing my own policy for caching.

This shows off some cool Gtk# 2.0 features (the tree node stuff) and some cool C# 2.0 features (the delegate stuff). Also, I am using a very cute hack, the xml serializer, to read the data.

String Freezing

2005-08-06T16:29:00.000-04:00

Whidbey has a very cute feature in it's ngen (it's ahead-of-time compile solution). Traditionally, string literals in .NET assemblies are stored in a string heap. When they are loaded from the assembly (using the IL ldstr opcode), the runtime allocates a new object and does a memcpy of the data (on some platforms chars have to be byteswapped, but same idea). Why does this copy need to happen? The first 8 bytes of an object consist of a pointer to a VTable (which holds the object's type's identity, including the data needed to make virtual calls) and a (normally null) pointer to a "monitor" that can be used to lock the object. Now, this is a fairly large waste of memory. First, we have to allocate the string in the GC heap in each process. Second, by reading the string from metadata, we have paged it into memory there (but that is shared between processes). The traditional solution to this (as is implemented in C programs) is to store strings in the .rodata section of shared libraries. This way, they can be shared between processes. (C also does a cute hack taking advantage of the fact that strings are \0 terminated. If you have "123" and "abc123" as literal strings in the same program, it stores "abc123\0" and the string "123" is just "abc123" + 3). Doing something like this should be simple in the aot format. The string data just needs to be copied to a readonly section. However, there are two challenges. First, the VTable for string is allocated in dynamic memory. How can we know its address at AOT time. I can think of two possible solutions: Mono statically links the JIT and Runtime into a single executable. Static executables never get relocated, so we can pre-allocate the .data section in the mono runtime. We know that this pointer won't change (except if mono is recompiled; some sanity check would be needed). However, this has a very large disadvantage: applications embedding mono could never take advantage of this. A second, harder, but much better (IMHO) solution is to implement a system like the Windows dynamic loader. Jason Zander explains how this works here. To give a sort summary, in Windows, you need to say that your .dll should be loaded at a specfic address in virtual memory. If that address can't be found, the operating system goes around and changes all references that depended on this location. If we use this solution, the AOTd mscorlib.dll would simply hold the string vtable. This solution is alot better because it provides us with advantages beyond string freezing. We avoid the need for a GOT/PLT like structure. Also, we could precomputate vtables, and possibly other metadata structures, and store them in readonly memory; this would greatly reduce the cost of managed code. The disadvantage is that we need to help developers find available virtual address space. Also, if there are virtual address space conflicts, we probably can't use the aot'd file. This solution also takes a fair bit of work. For some more information about Whidbey improvements in Microsoft's runtime see ricom's blog. Also, Jeroen Frijters wrote about string freezing Idea I had right after I published: string literal bloat seems most likely to matter in a GUI application. However, in that case, we also have the issue that we need to convert the .NET style string to a C style string when we call Gtk+. Would it make sense for us to also pre-cache converted strings so that they too could be shared?

I'm back!

2005-07-20T13:48:00.000-04:00

I've been blogless for a while. Some person in Europe called our ops at 3 am in the morning talking about an emergency (now, to be fair, that was probably a reasonable time for them). The emergency? codeblogs.ximian.com had (GASP) porn spam! Novell was sponsoring porn! Our friendly ops, not happy about the rude awakening, decided that the easiest solution was to shut down the server completely. Lazyness has caused me not to have a blog since then.