This week I spent time getting acquainted with the research,
department and school. I spent most of my time reading about programming with threads and the types of bugs threads introduce. I read papers about
detecting bugs in code such as memory leaks, dangling pointers
and data races. I also read through many of the research papers
published by the OPERA
research group I am working with. There is a lot more for me to learn before
I can get elbows deep into the research. I would have been nice to
have arrived with a running start so I can immediately work, but unfortunately
that wasn't the case.
For the dynamic thread bug detecting project, I started running through MySQL
bug reports in hopes of finding race bugs. This is harder then you think because
sometimes the developers didn't know what was causing the bug. I also had a
difficult time because I never used MySQL so I didn't know what some of the
reports were talking about. I found that looking at the patches and comparing
the patches to what was said sometimes helped, but sometimes I needed the source
code. However, MySQL doesn't keep a repository of their older releases, and
the newer releases were unhelpful.
On Wednesday, we had a "reading group" meeting where two students present papers.
Professor Zhou (YY) requested that the other DMP student (Raluca) and I each present
later in July. I have to admit that I am not a fan of the idea, but it will
be good for me. I am more concerned at the fact that all of the other students
have more expertise in the subject then I, so they may grill me on things I do
not know. However, this experience will be good for me, it will allow me
to work on my presentation skills. When I return
to Wellesley I am going apply to present in the fall Tanner Conference. The Tanner
Conference is what I like to call the "what I did last summer" conference were people
present their work, their experiences and how they changed the world during the summer.
Thursday, Raluca, Shan and I met with YY about the bug project. We concluded that we
needed to explore more bug sources. I was happy to be able to come up with ideas
of other possible types of open source projects that we can look through (such as Mozilla,
KDE, gnome, Open Office, etc. I agree that it is important to look for more then just servers
to get a sense of the types of bugs that occur. I can see that different types of bugs are
bound to happen on different types of software. I then spent the rest of the day trying
to find different open source projects that had bug reports (graphics API, games, etc).
I was able to push for an "extreme management" meeting. The meeting occurred on Friday.
We weren't ready to come up with anything concrete so we decided to look at online forums
to get a sense on how different problems were troubleshooted and solved so we can see
the dependencies that were in play. I choose to look at Linux troubleshooting. I am a
little concerned that this project will not happen because the other students are busy,
but I will be making extra pushes for it because if we can get a good start, I would like
to work on it for the rest of the summer.
Also on Friday, we had a brainstorming session. We talked about transitional memory.
I really had no clue about what transitional memory was, so I couldn't participate
much. But now I have an idea of what other work is happening in systems threading
This week i am spending most of my time reading through
bug reports on Mozilla's bugzilla, I had a large list
to read my way through. The reason we need to do this is
because it gives us motivation to continue with the project.
If it turns out that the kind of bugs we want to address
are rare, we shouldn't continue the direction we want to continue.
This isn't an easy
task because I do not know how the software Mozilla has are
implemented, and I need to know the nature of the threading
they use so I can determine if the bug report I am reading
is a concurrency issue. This is not an easy task,
however I found tools to help such as their lxr (Linux cross-reference)
web pages where I can click on a function name, variable, etc and find
all the other places in the code that it was used. I learned
the hard way that it is much better to work a bug at a time
then to go through the bugs to rule out the non threading induced
The other task I am working to read through Linux troubleshooting
on forums to see how we can use a dependency tree to address
troubleshooting problems. It looks somewhat promising because
many applications are dependent on other applications in unexpected
At this week's brainstorming session, we realized that we had
more project ideas then students. It is amazing how creativity
and curiosity can thrive when given the right environment.
Another week, another dollar. (Just kidding!)
Today (Monday) Raluca, Shan and I met to discuss the bug
reports. We concluded that there was one more type of bug
that we should address: ordering bugs. Sometimes some
function is intended to happen before another function, and
if this doesn't happen: bug! We can address this type
of bug in the next step of our research.
I continued doing some reading for the system management project.
I found one paper called
Configuration Debugging as Search: Finding the Needle in the Haystack
that I particularly liked. It tries a time based approach in finding bugs.
Often when a system has a problem, it has it at some point in time
before that point the system was working, after that point the
system has a bug. The paper uses a time traveling file system
to help the user pinpoint when a bug occurred and what change
happened at that time. Before I left Wellesley for the summer,
I talked to a professor out potential thesis ideas. He brought
up the idea of a time traveling/journaling file system. It may
be interesting to do a project like that for bug detection during
my senior year. It will not be original work, but I am told
at the undergraduate level it doesn't have to me original. Maybe
I will be able to extend the work, I just need a chance to
read through it more.
Monday was a busy day! I also had a meeting to talk about the system
management project. We needed to decide on a granularity.
We decided that we should not try to debug single programs
this way, instead we should look at interactions between
programs. I agree with this approach.
(Wednesday) Now that I have had a chance to look through
Linux troubleshooting more closely, I am a little worried.
The dependency debugging may not be so useful after all
because a lot of the problems I found were internal
to an application's configuration, and not inter-application.
We need to be very careful in how we approach this. I hope
that this can also be used as a way to do distributed debugging
otherwise it may turn out to not be so useful.
In the bug report realm, I have moved on to looking
for race bugs in gnome and KDE. I have realized
that their bug tracking isn't to thorough as Mozilla's
making it much harder. Also gnome doesn't have lxr, I
have been spoiled by Mozilla! So far I haven't found anything
different with gnome or KDE, in fact they mostly
have the "classic" types of race bugs that most race
detectors can detect already.
At a meeting with Shan, Raluka and YY, we decided to move on
with some implementation. Next week I will be using the
application called pin to log memory access, then I
will use it to dump out all the define-use traces.
This week I got acquainted with
Pin, a tool used for dynamic instrumentation of programs.
It allows us to inject code into binary executables that runs
during the execution of the binary so we can monitor things
like memory accesses and threads. There are a couple of pages
of not so clear instructions, so it took a while to get any of the
sample pintool programs running. Along the way I found one other
resource that may be useful in the future, an online forum for pin.
So If I have questions, I can post there. The Pin tutorial
made emphasized that some instrumentation you add is executed only
once because it us executed in its JIT compiler (which caches code
for reuse) and the analysis code may be executed many times.
I decided to study this more because creating an efficient tool
is important to us.
I have been spending lots of time playing with Pin as it is
not very easy to use. For example, it makes heavy use of callback
functions while not documenting the creation of callbacks clearly.
However, I was eventually able to persuade Pin to spit out relevant
information like thread ID, memory access location and type of memory
access. One problem that I see is that Pin monitors every last memory
access including ones used to setup the C program, and so even with
a trivial C program that writes one thing to memory, I get pages
of memory accesses that are useless to us. There must be
a way to structure this to get only relevant information. I will
talk to Shan to see how she did this in her AVIO tool.
I have been continuing work on the system management project,
and now I am doubting more and more that that granularity we
chose to study is useful. Most problems I have seen are either
intra-application or networked, not much in between (which is
what we are looking for.)
On Friday, Shan had a paper deadline. The paper she wrote
was results of our bug survey. So I spent a good amount of time
looking through gnome bug reports for her. In the end, they
didn't prove that useful. I helped her by reading through
her paper and making revisions. I realized that if I read through
papers in a more editing state of mind, I read through them more
carefully and retain/understand more from the paper. Hopefully
this helps my paper reading strategy in the future.
Now that I have a good idea on how Pin can be used, YY advised
me to do a feasibility study so we can see if it is worth our
time to code something that will detect define/use relationships.
So I have been going back though Mozilla bugs that can be
detected using a Define-Use criterion. The biggest thing I
have noticed is that some bugs are hard to pinpoint to a certain
variable/memory access. This makes it hard to analyze. I wonder
if it would be worth it to also explore the relationship with
a larger granularity- function calls. This would be much
more ugly to look at then variables because we would potentially
have to pay attention with the arguments passed. It is probably
not worth it, but it was a nice thought while I was having it.
The one bug that I saw that is troubling me the most is one
that involves the ordering on queries made to an LDAP database.
When queries are made to the database, we are working with
another library. Normally, we would want our Pin code
to ignore calls make in different module because we are making
the assumption that those modules have no bugs. However, when
we make that assumption, we miss bugs like this because the
actual memory access is buried in the LDAP library. Is
it feasible to pay attention to memory access in local
code and look at orderings of calls to other libraries as well?
This may give us way too much overhead. Although we would
like to build something that finds every concurrency related bug,
we need to worry about how efficient and memory intensive the
tool we build is. So as I continue my feasibility study, I
will keep this in mind.
I am realizing the important of pinpointing what exactly
is happening in real life Define-Use bugs. Because we
want this this to be a tool to use on actual applications,
we need to to know how to tune the algorithm. It may not
be enough to keep track of just the thread that most recently
wrote to a variable. Some of the bugs we are looking at
may have the same behavior in reading/writing to a
variable on a buggy run and a non buggy run. It may be
important to obtain some other information, such as the value
of variable in question. I am not working to get a very
deep understanding of the real life Define-Use bugs so
we can decide what is the best way to approach implementation.
This is not an easy task because the bugs we have found are
Shan, who I consider my graduate student mentor,
will be leaving next week, so I will continue the project
on my own. We met to discuss goals, and this is what we decided.
- Do a detailed feasibility analysis of the Define-Use bugs.
- Create a tool to dump information on Define-Use accesses.
- Analyze results.
I was able to get a deep understand of a couple of the
Define-Use bugs found in Mozilla. Neither of them are
the "ideal example" I am looking for, but even if one
of them was, I would still want to go through the rest
of the bug reports so I could get insight into the
different ways a Define-Use bug can surface. One of
the bugs turned out to be something that AVIO could
detect, as it can also be viewed as a atomicity violation.
In the other bug I was able to decipher, I wasn't able
to pinpoint the bug to a single Define-Use relationship
in memory accesses. The Define-Use error is happening
at a higher level. I am wondering if I will find
something if I trace a different variable,
but I would rather finish going through all of the bugs
first. Hopefully I will finish going through the bugs
next week so I can do some coding before my time here
is over. It is funny that I haven't done much coding
during my time here, I have mostly been just reading
On Friday we all went to Dairy Queen and enjoyed ice
cream cake during the brainstorming session. It
was a nice treat because there was a heat wave
that lasted most of the week. I was glad that
the presenters handed out printouts of their
notes because I couldn't hear what they were saying
since it was so noisy in the restaurant. Next week
the "Extreme Management" group I am working with
will be presenting in the brainstorming session.
We have a lot of catching up to do... woops.
This was a busy week. I continued my work with Mozilla
bugs, and I was able to crack one or two more. I still
haven't found a "perfect" example of a Define-Use bug,
but I am getting closer. I also worked to find
troubleshooting examples for the Extreme Management project.
On Monday, the Extreme Management brainstorming group
met so we can discuss our findings and get ready for
our brainstorming presentation on Friday.
On Thursday, I missed work
in the morning to take the GRE, and when I came back
a few of us met to discuss the Extreme Management
project. We put together a powerpoint and discussed
how package management systems work. I am a little
worried because we need to be
able to offer something fundamentally different
from what the package management systems offer.
If this project doesn't work out for graduate
level research, I may want to take it up as a thesis
topic, we will have to see.
Friday was extremely busy. In the morning, we had pizza
and the Extreme Management brainstorming session. We
are still somewhat unsure/uneasy about the fundamental
difference, but I think there is something there. Immediately
after the brainstorming, we went to Feng's thesis defense.
It was quite enlightening to watch, and he did a good job.
After the defense, Raluca and I each gave a presentation on
our summer work. After that we went out on the balcony and
had a small celebration in Feng's honor. The festivities
ended that evening, when we all went out to eat in the
group's traditional thesis defense dinner celebration. We
ate in Kennedy's, a American/French fusion restaurant
located in the southern edge of Urbana in the middle of
a golf course.
This week I finally pinned down a good example of a order
related bug. I also worked to get a define-use detector
prototype. At this point it keeps track of all the define-use
pairs. After heavily documenting my code and work, I am confident
that I am leaving Opera (namely Shan) with something that they
can use as a step toward furthering their research in concurrency