Friday, February 19, 2010

sbrk() is not thread safe

The sbrk() system call is a legacy relic of Unix systems before the era of virtual memory, for the purpose that a process may expand or shrink its heap memory in LIFO order. A typical programmer would never use this system call, but it is used to implement malloc() and free(). Modern OSes provide mmap() and munmap() to allocate and free virtual memory, but they still support sbrk() that is also backed by virtual memory. Many memory allocators, most notably the Doug Lea allocator, still prefer sbrk() when possible. When asked the question "why use sbrk() when there is mmap()," the response is often "why not?" We shall settle the account by answering why it is bad to use sbrk().

Out of the allocators that use sbrk(), there are two kinds: ones that recognize the non-contiguity of the sbrk() heap, and ones that do not. The sbrk() heap could become discontinuous because a mmap()'d region or a shared object obstructs the growth of the heap. We'll not pay too much attention to this here, but to focus on the other reason, namely that another part of the program could use sbrk() to request more memory, bypassing malloc(). It would be the result of a performance-critical part of the program implementing its own allocation strategy.

Suppose we write an allocator that, being a good citizen, would try to return memory back to the operating system whenever possible. Since sbrk() can only grow or shrink memory in LIFO order, it would only call sbrk() when it wants to free the last free memory block in the heap that it manages. Obviously, if we allow another part of the program to bypass our heap management and use sbrk() directly, we need to be careful that we can release our free memory block only when it is the top of the heap.

The situation becomes more complicated in multi-threaded programs. A good allocator would use locks and scalable data structure to manage the heap, but it eventually has to acquire or release memory using sbrk(). We can assume that sbrk() system call is atomic, but we will show that sbrk() is still not thread-safe.

Let's say sbrk(0) indicates that the top of the heap currently lies at the end of our free block that we want to release, so the next step would be to call sbrk() with a negative number to shrink the heap. But before we get a chance to do that, we're preempted by another thread that calls sbrk() to expand the heap. Once the other thread is done, we proceed to shrink the heap by the amount we previously determined. We violated the LIFO order, and ended up shrinking the memory the other thread requested.

The problem is that atomicity of sbrk() does not guarantee the consistency of the state of the heap. There is, however, a way to augment the system call with another argument that will make it thread-safe. The sbrk() assumes the following prototype:
void *sbrk(intptr_t increment);
We can regard sbrk() as a function that adds an integer by an increment atomically. Inspired by how compare-and-swap works, we shall modify the function as follows:
void *sbrk_safe(intptr_t increment, void *expect_top);
The new function will only cause the heap to shrink or grow if the expect_top pointer, as seen by the caller of sbrk_safe(), is still the same as the actual heap top. If not, an error value is returned; the caller should refresh its own snapshot of the heap state, and then decide if it wants to try again. This allows each caller of sbrk_safe() to maintain transactional integrity.

We showed that sbrk() in its current form is not thread-safe even if it is atomic. We showed that it is possible to fix by proposing a change of the function definition. However, the ultimate verdict is that it is time to stop using sbrk() altogether. We should all be using mmap() instead.

Update (Feb 22): apparently phkmalloc uses sbrk() as its primary way of requesting memory, and its successor jemalloc still allows the use of sbrk() through MALLOC_DSS option. Jemalloc tries to protect sbrk() with a mutex, acknowledging that it does not protect against third-party use of sbrk().

19 comments:

Unknown said...

Hello,

Found your blog as a top hit for running Chrome on RHEL5, and poked around from there. Most of Amazon runs on RHEL, it would be nice to have Chrome on it, nicer if it would run out of the box.

Interesting blog.

What's your employment situation? We'd love to interview you at Amazon.com.

Likai Liu said...

I have to admit and apologize for the fact the instruction about running Chrome on RHEL5 is a bit terse. I have hacked together a script to automate building all the dependencies from source. Let me know if you want to help me polish it, and perhaps make it useful for all the people running RHEL. You can find my contact information at http://cs.likai.org

john said...

Thank you.

Nancy Jones said...

Besides my C course, I have a job and family, both of which compete to get my time. I couldn't find sufficient time for the challenging C assignments, and these people came in and saved my skin. I must commend them for the genius Programming Assignment Help. Their C Homework Help tutors did the best job and got me shining grades.

Nancy Jones said...

I am looking for a Statistics Assignment Help expert for Statistics Homework Help. I have struggled enough with statistics and therefore I just can't do it anymore on my own. . I have come across your post and I think you are the right person to provide me with SPSS homework help. Let me know how much you charge per assignment so that I can hire you today.

Nancy Jones said...

Matlab Assignment Help helped me to complete my seventh Matlab assignment, which was also the best-performed! It scored 92/100, which I've never scored before on any other assignment/exam in my lifetime. Otherwise, their service was as quick as usual. The delivery was also on time. I'm now requesting to use this same programmer multiple times. He seems the best in Image Processing tasks. Meanwhile, I'll ask for more Matlab Homework Help soon.

Nancy Jones said...

I have just come across your post and I believe this is exactly what I am looking for. I want an economics assignment help from a tutor who can guarantee me a top grade. Do you charge per page or does it depend on the
bulk of the economics homework help being completed? More to that if the work is not good enough do you offer free corrections.

Maria Garcia said...

The ardent Programming Homework Help tutor that nailed down my project was very passionate. He answered my Python questions with long, self-explanatory solutions that make it easy for any average student to revise. Moreover, he didn't hesitate to answer other questions, too, even though they weren't part of the exam. If all Python Homework Help experts can be like this then they can trend as the best Programming school ever online.

Maria Garcia said...

Hey STATA homework help expert, I need to know if you can conduct the Kappa measurement of agreement. This is what is in my assignment. I can only hire someone for statistics assignment help if they are aware of the kappa measurement of agreement. If you can do it, then reply to me with a few lines of what the kappa measure of agreement is. Let me know also how much you charge for statistics homework help in SAS.

Maria Garcia said...

Me and my classmates took too long to understand Matlab Assignment Help pricing criteria. we're always grateful for unique solutions on their Matlab assignments. Matlab Homework Help experts have the right experience and qualifications to work on any programming student's homework. They help us in our project.

Maria Garcia said...

Hi, other than economics assignment help are there other subjects that you cover? I am having several assignments one needs an economics homework help expert and the other one needs a financial expert. If you can guarantee quality work on both then I can hire you to complete them. All I am sure of is that I can hire you for the economics one but the finance one I am not sure.

Hanna Bell said...

Hello. Please check the task I have just sent and reply as soon as possible. I want an adjustment assignment done within a period of one week. I have worked with an Accounting Homework Help tutor from your team and therefore I know it’s possible to complete it within that period. Let me know the cost so that I can settle it now as your Accounting Assignment Help experts work on it.

Hanna Bell said...

That is a huge number of students. Are they from the same country or different countries? I also want your math assignment help. I want to perform in my assignments and since this is what you have been doing for years, I believe you are the right person for me. Let me know how much you charge for your math homework help services.

Hanna Bell said...

I don’t have time to look for another expert and therefore I am going to hire you with the hope that I will get quality economics assignment help .Being aneconomics homework help professor I expect that your solutions are first class. All I want to tell you is that if the solutions are not up to the mark I am going to cancel the project.

Hanna Bell said...

Hey there, I need an Statistics Homework Help expert to help me understand the topic of piecewise regression. In our lectures, the concept seemed very hard, and I could not understand it completely. I need someone who can explain to me in a simpler way that I can understand the topic. he/she should explain to me which is the best model, the best data before the model and how to fit the model using SPSS. If you can deliver quality work then you would be my official Statistics Assignment Help partner.

Sarah Wilson said...

Just what I was looking for. I am struggling with my accounting assignment. I want an Accounting Assignment Help tutor to offer me two services. One is to complete my accounting assignments and the other is to provide me with online classes. I believe you are experienced enough to offer both Accounting Homework Help and online classes. I know you charge assignments based on the bulk. Tell me how much you charge for the online classes per hour.

Sarah Wilson said...

As much as there are discouragements, it is true that mathematics is hard. Like in my case, I was never discouraged by anyone about math but I still find it very hard and that is why I am requesting your Math assignment help. I am tired of struggling with mathematics and spending sleepless nights trying to solve sums that I still don’t get right. Having gone through your Math homework help, I am sure that I will get the right help through you. Please tell me what I need to be able to hire you.

Sarah Wilson said...

I have submitted my assignment to your website without any challenges. The economics assignmenthelp expert handling my assignment has already contacted me and I am certain that my work is underway. I am just hoping that I will get quality economics homework help. I have a lot of hopes in you and I am just hoping that you will not disappoint me.

Sarah Wilson said...

How much do you charge for a Statistics Assignment Help task? Take, for statistics assignment experts my case, where I need you to provide me with the Statistics Homework Help on plotting a scatter plot with a regression line? How much should that cost? Do you charge on the basis of the workload or have a constant payment?