Lock-free Ring Buffer in C++

In a multi-threaded program, we have to make sure that the shared data are thread safe. Usually, we employ some kind of lock (mutex, semaphore etc) to achieve it. However lock itself is expensive. If the lock is removed and in the same time the data is still thread safe, the performance will be improved a lot. There are lots of researches on lock free data structures. Most of them require the hardware to provide CAS. These methods are intricate in terms of implementation and correctness. They need to deal with such problems as ABA Problem as well.Those methods are for general cases. They can be applied to the situation where there are many threads and each one can have read and write acc/ess to the shared data. But when looking into a special case, and studying its properties, we can find a simpler and more efficient lock free data structure.

The special case is the single producer single consumer. This is a simple scenario and it is not uncommon. In this scenario:

  1. There are only two threads accessing to the shared data.
  2.  One of them only reads the data. The other only modifies the data.
  3. Data is written at one end while it's read at the other end.

A queue is usually used to pass data between threads. But I would like to use the ring buffer. This is because:

  1. A queue is usually implemented by using a list. There is memory allocation for each element added. Memory allocation is expensive and there is a global lock in dynamic allocation in C/C++ (you can search for "lock-free malloc" if you're interested).
  2. A ring buffer is usually implemented by using an array. we can allocate memory in bulk. Thus reduce the times to allocate memory. e.g. instead of allocating 10 elements 10 times in a queue, we can allocate an array with 10 element only once.
  3. We can achieve spatial locality by using an array. It is hard to achieve it by using a queue.

There is a drawback of an array. The size of an array is fixed. So we cannot put more elements into the ring buffer when it is full. But there is a way around it.

First let's look at a simple implementation of a lock-free ring buffer in a single producer single consumer context (refer to this link for more information about ring buffer). Then we will see how it works and why it works. At last, I'll address the limitations and improvements.

This is the implementation. It may be improved later.


class RingBuffer
{
public:
    RingBuffer();
    int read(int *result)
    int write(int element);private:
    unsigned read_index;
    unsigned write_index;
    static const unsigned buffer_size = 256;
    int buffer[buffer_size];
};

RingBuffer::RingBuffer() : read_index(0), write_index(0)
{
}

int RingBuffer::read(int *result)
{
    unsigned local_read = read_index;
    if (local_read == write_index)
    return 0;++local_read;

    if (local_read == buffer_size)
        local_read = 0;*result = buffer[local_read];

    read_index = local_read;return 1;
}

int RingBuffer::write(int element)
{
    unsigned local_write = write_index;++local_write;
    if (local_write == buffer_size)
        local_write = 0;

    if (local_write != read_index) {
        buffer[local_write] = element;
        write_index = local_write;
        return 1;
    }
    return 0;
}

There are only two variables that we're interested in. They are read_index and write_index. The variable buffer is where the shared data will be in. And we need to guarantee the access to the data in buffer is thread safe. That is what read_index and write_index for. Any writes won't go pass read_index and any reads won't go pass write_index either.

Note that in single producer single consumer, there are only one thread reading (called reader thread) and only one thread writing (called writer thread). And the reader thread will only call RingBuffer::read() and writer thread will only call RingBuffer::write(). So the read_index is only changed by the reader thread and write_index is only changed by the writer thread. Also note that they are changed only when the actual read/write is done. So in read(), before read_index is changed, writer thread won't write to any places after read_index. That is also where reader thread will read data.  So the writer thread won't overwrite any data. This is true in writer(). The reader thread won't read from places after write_index.

Let's take an example to see how it works. Say the size of the ring buffer is 256 and write_index = 200 and read_index = 100. The writer thread has already writen to the cell 200, and the reader thread has read data from up to cell 100.

0 ... ... ... 100 ... ... ... 200 ... ... ... 255

The cells in blue are safe to write in and the cells in red are available to read. The reader thread first checks whether read_index (100) is equal to write_index (200). It is not, so it will read the element at 101. If read_index goes to 200, the reader thread won't get any element because read() will just return when read_index == write_index, which means that the reader thread never gets a chance to read from any cells in blue including the cell 200. So either the reader thread will read valid data or it won't read any data at all. This is the same when we analyse the writer thread. The writer thread never overwrites the cells in red, including the cell 100. The writer thread will always write to an cell that is safe to do so.

But why are there local_read and local_write? When the reader thread reads the buffer, the writer thread will probably try to write to it. Since read_index is used to prevent the writer thread from writing to the red cells. It shouldn't be changed during this process until the reader thread has finished reading.  So we use local_read to tell the reader thread where to read the element. Once the reader thread gets the element and it is assigned with the value local_read, the writer thread can immediately write to that cell. It won't corrupt any data because the element at that cell is already read.

That is how read_index and write_index together protect the shared data. But to make it actually to work as we expect, we need to address some technical details. There are two major problems we need to take into consideration: atomic operations and reordering.

  • atomic operations

Both the reader thread and the writer thread can access read_index and write_index. The read/write of them must be atomic operations for this to work properly. Otherwise, one thread may get stale data. On x86/x86_64 integer read/write are atomic if they're properly aligned. Thus we have to check with the compiler how they align integers. And I believe most will do them correctly.

  • reordering
  • Compiler reordering

The compiler may reorder instructions to optimize the program. Let's take a look at this snippet from read():

*result = buffer[local_read];     inst. 1
read_index = local_read;          inst. 2

The compiler may emit inst. 2 before inst. 1. If so, read_index is changed before the reader thread reads the element.  If the writer thread happens to run, can it write to read_index? NO. We don't need to worry compiler reordering here.
But it is not OK in write().

buffer[local_write] = element;     inst. 3
write_index = local_write;         inst. 4

If inst. 4 is moved above inst. 3. Write_index is updated before the writer thread writes to buffer[local_write]. That will allow the reader thread to read from buffer[local_write], which will read stale data. To deal with it, I make local_write volatile to have the compiler not to optimize reads/writes of local_write and make sure inst3. is executed before inst. 4. But don't need to make read_index or write_index volatile. (refer to this and this if you're interested in volatile.)

We still assume it is on x86/x86_64. The CPU won't move reads around other reads, writes around other writes or move writes before reads. It only moves reads ahead of writes. Let's look at read(). It reads read_index to local_read, modifies local_read, reads the element at local_read to the result, and then modifies read_index. The update of read_index is not executed before the element at local_read is written to result. Even if modification of read_index runs before reading the element in local_read due to compiler reordering, we know that the writer thread won't write to read_index. The data is still safe.

There are some limitations to this implementation.

  1. We assume that atomic operations and reordering on x86/x86_64. It is not necessarily true on other platforms.
  2. It only reads/writes one element at once. It would be better to have such interfaces int read(int *array, int max_size) and int write(int *array, int max_size).
  3. The array won't grow. This implementation of ring buffer won't hold more than 255 elements. But what if the writer thread writes more than that but reader thread cannot catch up? We need to think of a way to "expand" the ring buffer. The idea comes from the possible implementation of deque in C++. But instead of vector of vectors, a list of such ring buffer is used. If the current ring buffer is full, we can append a new ring buffer to the list and the writer thread writes to the new one. That's it. Again, we need a lock-free list. And when a ring buffer is empty after reading, we need to release them if they are dynamic allocated. There are two articles regarding lock-free queue.  http://www.drdobbs.com/parallel/208801974 and http://www.drdobbs.com/parallel/210604448?pgno=1. I believe you can implement it and you won't worry about the capacity of a single ring buffer.

Javascript Paging

I wanted to have my own home page that would display all I published on Twitter and other blogger services. So I learned Javascript and wrote one myself. It was easy to have the content displayed on the web page. It displays the latest tweet followed by a blog article. When you click on the right margin, the next article will appear. Similar to that, when you click on the left margin, the previous article will display. There was a problem though. When the article happens to be long, it would take much space from top to bottom. Then I wanted to add paging and the area to display the article is fixed. If the article cannot fit into that area, it only displays what it can display and the remaining parts are hidden. When the right margin is clicked on, the next part is going to display.I spent a lot of time looking for a way for paging. There are many methods and plugins to do this. But they seem not so useful in my case. They provide simple and convenient methods to do the paging. Some assume that every content for each page is already in the page (technically speaking, in DOM). When paging occurs, they just display the next element and hide the current one. Others retrieve new content when paging occurs and replace the old content. But in my case, I have the whole article and need to implement paging on it. That means I also need to "divide" an article into parts.

I found this blog Javascript Dynamic Paging (MooTools Pager). I wished I can just copy and paste. But I was using JQuery framework. However, after reading some lines of code, I guessed I could implement it in JQuery. That's why I couldn't copy & paste and I even didn't bother to read the blog at the first time.

Here is the idea to do the paging.

Let's say the blue box (see below) is where I want to display the article.

Without paging, the article would look like:

Line 1
Line 2
Line 3
Line 4
Line 5
Line 6

 

 

With paging, it will be:

Line 1
Line 2
Line 3
Line 4
Line 5
Line 6

"Line 6" is hidden. Here is the code for the above example.


<div id="article" style="border-color: blue; border-style: solid; border-with: 1px; height: 100px; overflow: hidden; width: 100px;">
Line 1<br />
Line 2<br />
Line 3<br />
Line 4<br />
Line 5<br />
Line 6</div>

Then, we need to add a new <div id="slider"> around the article and inside the <div id="article">.
And when paging occurs, we just need to slide the <div id="slider"> up or down. And also have <div id="article"> hide any content outside its bounds, as shown in the following:

Line 1
Line 2
Line 3
Line 4
Line 5
Line 6

To go to the next page, we need to move <div id="slider"> up by the height of <div id="article">. After that, it will display:

Line 1
Line 2
Line 3
Line 4
Line 5
Line 6

In the above example, the content is statically set in HTML. But in my web site, the content is retrieved from the server. I use AJAX here. After the content is returned, I create a <div> element and insert it in to <div id="article">. Then everything goes well until we come to the end of the article. If we keep moving the inner <div> up, it will display nothing if we've already displayed the last part of the article. If we go from the above example to the next page, we get

Line 1
Line 2
Line 3
Line 4
Line 5
Line 6

The solution is to compare how far the <div id="slider"> moves up and the height of the article. If the distance it moves is larger than the height of the article, then it has displayed the last part of the article. So far, the problem becomes finding the height of the article, or the inner <div>. I tried it many times to find it very tricky. We don't get the size of a <div> unless it is in a DOM. What we need to do is to add <div id="slider"> to <div id="article">. After that, We can get the height of the <div id="slider">, that is, the height of the article.

To put them together, I've managed to implement a Javascript paging method. Take a look at kceiw.me. You can find the source. It is without minification.

Vim plugins for C++ development

The plugins can be found from http://www.vim.org/scripts

1. Tagbar
It displays tags of the current file in the sidebar. You don't need to create a
tag file by using ctags. These tags include macros, namespaces, classes, and
function signatures, etc.
Personally speaking, It does better than taglist.

2. CCTree
It is used to display the calling tree of C code. It needs cscope file

3. clewn
This plugin helps you interact with GDB. Once you have to debug your program,
it is very helpful. You can see the source code in your vim buffer, send
command to GDB and see the result from another vim buffer too.

4. clang_complete
It helps to complete C/C++/Objective-C code in your development. Besides that,
it also displays warnings and errors regarding your code.

5. refactor
It provides some basic functionalities to do refactoring for C/C++.

6. stlrefvim
View STL reference within VIM.

7. CRefVim
View C reference within VIM.

How to Crash a Macbook

I found a rather easy way to crash a Mac.

First, You need to have two or more partitions.
Second, delete the directory /var/vm.
Third, create a symbolic link. ln -s /The/Other/partition/directory
/var/vm. /The/Other/partition/directory is at another partition other
than the one where /var is at.

Then you continue to use your Mac for some time, you will find at least
one program crashes. Then you may decide to reboot your mac to see
whether the program will become normal, you must find that your mac
could not start again.

Don't be panic. You can solve it. Use your Mac installation disc. But
you don't need to reinstall your system. You can open a terminal, delete
the symbolic link /var/vm and create a new directory /var/vm. Then you
will find your crazy mac become normal.
Why?
I think this should be a bug in Mac.
/var/vm is the directory where the swap files are at. Mac seems to use
this directory before it mounts the other partition. So if /var/vm is a
symbolic link to other partition, Mac could not use /var/vm at all when
it starts, because other partitions are not available yet.

And the swap files can become very large. They may use up the all the
disk space. They will make the system rather slow.

How GDB implements break command

When you want to add a breakpoint, you usually use the command "break". GDB will first parse the command, and find the address, as described here. But what's the next?

GDB will create a breakpoint after it parses the command and finds the address and the symbol table . The breakpoint is represented by the type struct breakpoint (see create_breakpoint). At this point, GDB only creates the structure and adds it to the collection of breakpoints. It does not really insert them. The insertion only occurs before the inferior starts to run. For example, when the function proceed is called, which will make the inferior run, it will call insert_breakpoints to insert the breakpoints in the collection of breakpoints.
When a breakpoint is hit, a trap, a signal or whatever will cause the inferior to stop. At this point, GDB will take over of it and handle the event first. It calls the function handle_inferior_event. It will check the reason why the inferior stops. And it will detect whether there is a breakpoint hit. Remember you can add conditions to breakpoints. If the conditions is false, even if there is a breakpoint hit, GDB won't do anything. GDB stops the inferior only when a breakpoint is hit and the conditions are true.