Talk:COMP 3000 Essay 2 2010 Question 6

Alright so its due tomorrow. I was hoping to get an idea of when everyone will be posting there completed sections thanks. --Azemanci 03:56, 2 December 2010 (UTC)

Actual group members

- Nicholas Shires nshires@connect.carleton.ca

- Andrew Zemancik andy.zemancik@gmail.com

- Austin Bondio -> abondio2@connect.carleton.ca

- David Krutsko :: dkrutsko at connect.carleton.ca

- Andrew Bujaki ==> abujaki [at] connect.carleton.ca

If everyone could just post their names and contact information.--Azemanci 02:57, 15 November 2010 (UTC)

IMPORTANT
THINGS WE NEED TO DEFINE:

• Happens-before reasoning
• Lock-set based reasoning
• Hardware Breakpoints
  

The prof seemed to be very focused on hardware breakpoints, so it is very important to define it well, and talk about it often, it looks like hardware breakpoints are the one thing thats setting DataCollider apart from other race detectors, so lets focus on it!
IMPORTANT

Who's Doing What

Research Problem

I'll do 'Research Problem' and help out with the 'Critique' section, the professor said that part was pretty big Nshires 20:45, 21 November 2010 (UTC)

The research problem being addressed by this paper is the detection of erroneous data races inside the kernel without creating much overhead. This problem occurs because read/write access instructions in processes are not always atomic (e.g two read/write commands may happen simultaneously). There are so many ways a data race error may occur that it is very hard to catch them all.

The research team’s program DataCollider needs to detect errors between the hardware and kernel as well as errors in context thread synchronization in the kernel which must synchronize between user-mode processes, interrupts and deferred procedure calls. As shown in the Background Concepts section, this error can create unwanted problems in kernel modules. The research group created DataCollider which puts breakpoints in memory accesses to check if two system calls are calling the same piece of memory. There have been attempts at a solution to this problem in the past that ran in user-mode, but not in kernel mode, and they produced excessive overhead. There are many problems with trying to apply these techniques to a kernel.

One technique that some detectors in the past have used is the “happens before” method. This checks whether one access happened before another or if the other happened first, and if neither of those options were the case, the two accesses were done simultaneously. This method gathers true data race errors but is very hard to implement.

Another method used is the “lock-set” approach. This method checks all of the locks that are held currently by a thread, and if all the accesses do not have at least one common lock, the method sends a warning. This method has many false alarms since many variables nowadays are shared using other ways than locks or have very complex locking systems that lockset cannot understand.

Both these methods produce excessive overhead due to the fact that they have to check every single memory call at runtime. In the next section we will discuss how DataCollider uses a new way to check for data race errors, that produces barely any overhead. http://www.hpcaconf.org/hpca13/papers/014-zhou.pdf

Moved from main page: (p.s thanks for the info!)Nshires 02:32, 2 December 2010 (UTC)

Just a few rough notes: Research problem / challenges for traditional detectors:

- data-race detectors run in user mode, whereas operating systems run kernel mode (supervisor mode).

- There are a lot of different synchronization methods, and a lot of ways to implement them. So it's nearly impossible to try and code a program that can catch all of them.

- Some kernel modules can "speak privately" with hardware components, so you can't make a program that just logs all the kernel's interactions.

- traditional data race detectors incur massive time overheads because they have to keep an eye on every single memory transaction that occurs at runtime.

--Austin Bondio 01:57, 2 December 2010 (UTC)

Contribution

What are the research contribution(s) of this work? Specifically, what are the key research results, and what do they mean? (What was implemented? Why is it any better than what came before?)

Proving that there is a problem in classic solutions to race detectors:
The main contribution that DataCollider provides is the unique idea of using hardware breakpoints in a data race detector. The question is why is a unique idea necessary. Why does DataCollider have to "reinvent the wheel". There has been a plethora of race condition testers invented in the last two decades, and all of the dynamic data race detectors can be lumped into three categories. They can either be lock-set, happens-before, or a hybrid of the two types of detection. The research team for DataCollider looked at several of these implementations of race condition testers to find ways of improving their own program, and to see that there are major problems in the classic ways of detecting race conditions.

Some of the programs that were referenced were:

• Eraser: A Dynamic Data Race Detector for Multithreaded Programs
  
• RaceTrack: Efficient Detection of Data Race Conditions via Adaptive Tracking
  
• PACER: Proportional Detection of Data Races
  
• LiteRace: Effective Sampling for Lightweight Data-Race Detection
  
• MultiRace: Efficient on-the-fly data race detection in multithreaded C++ programs
  
  

Eraser: A Dynamic Data Race Detector for Multithreaded Programs[1]
lock-set based reasoning

Eraser, a data race detector programmed in 1997, was one of the earlier data race detectors on the market. It may have been a useful and revolutionary program of its time, however, it uses very low level techniques compared to most data race detectors today. One of the reason why it is unsuccessful is because it only checks whether memory accesses use proper locking techniques. If a memory access is found that does not use a lock, then Eraser will report a data race. In many cases, the misuse of proper locking techniques is a conscious decision by the programmer, so Eraser will report many false positives. This also does not take into account all of the benign problems such as date of access variables. DataCollider used this source as an example of a lock-set based program, and why they are a poor choice for a race condition debugger.

PACER: Proportional Detection of Data Races[2]
happens-before reasoning

Pacer, a happens-before reasoning data race detector, uses the FastTrack algorithm to detect data races. FastTrack uses vector-clocks to keep track of two threads, and find whether or not they are conflicting in any way. Pacer samples some percentage of each memory access, (from 1 to 3 percent) and runs the FastTrack happens-before algorithm on each thread that accesses that part of memory. DataCollider used this source as an example of the implementation of sampling. Similar to Pacer, DataCollider samples some memory accesses, but instead of using vector-clocks to catch the second thread, they use hardware break points. Hardware break points are considerably faster, and cause DataCollider to run much faster than Pacer.

LiteRace: Effective Sampling for Lightweight Data-Race Detection[3]
happens-before reasoning

LiteRace, similar to Pacer, samples a percentage of memory accesses from a program. Where it differs is the parts of memory that LiteRace samples the most. The "hot spot" regions of memory are ones that are accessed most by the program. Since they are accessed the most, chances are that they have already been successfully debugged, or if there are data races there, they are benign. LiteRace detects these areas in memory as hot spots, and samples them at a much lower rate. This improves LiteRace's chances of capturing a valid data race at a much lower sampling rate. Where DataCollider bests LiteRace is based on LiteRace's installing mechanism. LiteRace needs to be recompiled into the software it is trying to debug, whereas DataColleder's breakpoints do not require any code changes to the program. This is a major success for DataCollider because often third party testers do not have the source code for a program.

RaceTrack: Efficient Detection of Data Race Conditions via Adaptive Trackings[4]
combination of lock-set and happens-before reasoning

RaceTrack uses a unique technique in order to detect data races. The program being debugged is run on top of RaceTrack as a virtual machine using the .NET framework, and it will examine all of the memory accesses that the program requests. As soon as suspicious behavior is exhibited, a warning is sent off to be later evaluated when the program terminates. RaceTrack uses this technique because several process intensive inspections of the state of the machine must be checked, and doing this on the fly is expensive. There are many problems with RaceTrack. It is very successful at detecting a vast percentage of data races, however, it has a high overhead and requires extreme amounts of memory. RaceTrack must save the state of the entire machine every time a warning is produced, and it also has to save each threads memory accesses to check which memory access "happened before". Since most warnings thrown are found to be benign, saving the state of the machine wastes computational power and memory. Long running programs also prove to be a problem, where the computer being debugged will run out of memory to store all of the warning states before the program terminates. It then will have to either increase overhead significantly to store the warnings on disk, or it will have to delete some warnings to make room for new ones.

MultiRace: Efficient on-the-fly data race detection in multithreaded C++ programs[5]
combination of lock-set and happens-before reasoning

MultiRace is another hybrid style race condition debugger that uses two unique algorithms. The first algorithm, Djit is the happens-before iteration, which INSERT STUFF HERE. The second is an improved iteration of the lock-set algorithm. MultiRace is the most similar program to DataCollider in terms of their goals. Both strive to decrease overhead to near standard running times of the program itself, and to increase the program transparency for maximum user compatibility. MultiRace itself is several orders of magnitude more complicated than DataCollider, but since MultiRace hides its complexity from the user with transparency, it is still simple to use. It is arguable that MultiRace is superior for detecting races for C++ programs, however, MultiRace is not compatible with any other programming language. Since DataCollider uses hardware breakpoints, the coding language of the program is irrelevant. Also, since DataCollider avoids using both lock-set and happens before algorithms, it is versatile enough to even debug kernels.

DataCollider is a very unique program. Most other dynamic race condition testers can be lumped into the three groups lock-set, happens-before, or hybrid. DataCollider, however, recognizes the errors of these styles of detection, and manages to avoid them completely. Even though there are issues with false positives and benign races, DataCollider provides very simple, versatile, and lightweight functionality in debugging a program. Future programs may take this unique style of race detection and add their own functionality to improve upon it. It could be that DataCollider could inspire a ground breaking solution to race conditions and how to detect them.

Background Concepts

Hey guys, sorry I'm late to the party. I'll get started with Background Concepts. - Austin Bondio 15:33, 23 November 2010 (UTC)

Critique

I'll work on the critique which will probably need more then one person and I'll also fill out the paper information section.--Azemanci 18:42, 23 November 2010 (UTC)

DataCollider: DataCollider seems like a very innovative piece of software. It’s new use of breakpoints inside kernel-space instead of lock-set or happens-before methods in user-mode let it check data race errors in the very kernel itself without producing as much overhead as its old contenders (it even finds data races for overheads less than five percent). One thing to note about DataCollider is that ninety percent of its output to the user is false alarms. This means that after running DataCollider, the user has to sift through all of the gathered data to find the ten percent of data that actually contains real data race errors. The team of creator’s were able to create a to sort through all of the material it collects to only spit out the valuable information, but the creators still found some false alarms in the output . They have noted though that some users like to see the benign reports so that they can make design changes to their programs to make them more portable and scalable and therefore decided not to implement this. Even though DataCollider returns 90% false alarms the projects team have still been able to locate 25 errors in the Windows operating system. Of those 25 errors 12 have already been fixed. This shows that DataCollider is an effective tool in locating data race errors within the kernel effectively enough that they can be corrected.

feel free to add/edit anything Nshires 02:54, 2 December 2010 (UTC)

Right on thanks for that I was just about to start writing a section on data collider I'm not really sure what else we can critique.--Azemanci 03:11, 2 December 2010 (UTC)

I added a few things to the what you wrote and I also moved it to the main page. --Azemanci 03:22, 2 December 2010 (UTC)

Nice :P maybe something on how they tested their program, and if thier testing was sufficient? Nshires 19:11, 2 December 2010 (UTC)