6 ms·
Nah Lock: A Lock-Free Memory Allocator
- Karunamon 12y agoDoes the __ in front of "nalloc" have a special meaning?
- EpicEng 12y agoIdentifiers which begin with double underscores are reserved for the implementation
- jcr 12y agoUnfortunately, it seems the git repository mentioned is not publicly available. I searched for 'apodolsk' and found one on github, but the nalloc code is not there. Luckily, it seems the author is on HN (user: "gosu"): https://news.ycombinator.com/item?id=8613038 https://news.ycombinator.com/item?id=8613038 I toyed with scalable allocators for a course a few years back. It's a little embarassing, but if you want to see what the costs actually are: http://www.andrew.cmu.edu/user/apodolsk/418/finalreport.html https://news.ycombinator.com/item?id=8613156 https://news.ycombinator.com/item?id=8613156 With luck he'll notice that his nalloc work is on the front page of HN, and possibly tell us if the nalloc code is available somewhere.
- jwise0 12y agoIf you have a local AFS install, it looks like you can clone from: /afs/andrew/usr2/apodolsk/repo/nalloc_nonbare It looks like the public AFS/web gateways around don't seem to support .git directories (huh!). But, I have cloned it and mirrored a git bundle: http://emarhavil.com/~joshua/nalloc.bdl http://emarhavil.com/~joshua/nalloc.bdl wget it, then 'git clone nalloc.bdl nalloc'.
- bowlofstew 12y agoThat isn't working for me. Probably easier to just wget from http://www-afs.secure-endpoints.com/afs/ANDREW.CMU/usr2/apodolsk/repo/nalloc_nonbare/ http://www-afs.secure-endpoints.com/afs/ANDREW.CMU/usr2/apod...
- haberman 12y ago> After writing an email to Kayvon professing "correctness", I realized that I had a very bad and obvious race condition: [some thread reads an old pointer, leading to segfault]. Is there a more clever (lockfree) way than having a locked instruction on the common path in order to satisfy a rare edge case? While I don't fully understand the details of the allocator design described here, this sounds very much like the "safe memory reclamation" problem that plagues lock-free algorithms. I run into this almost every time I want to do something interesting that is lock-free. It's a huge bummer. The basic problem is this: anytime you want to be able to free memory in a lock-free data structure, there is almost always the risk that some other thread has read a pointer to that very memory, has the pointer sitting in memory or some register, and then goes to sleep (ie. is preempted) before it can actually dereference it. These threads are "ticking time bombs", so to speak. If you free the memory, the thread will crash when it wakes up and dereferences the memory. Every simple solution to this problem you're tempted to invent doesn't work. The main solution to the problem in the literature is Hazard Pointers (http://en.wikipedia.org/wiki/Hazard_pointer http://en.wikipedia.org/wiki/Hazard_pointer), which also solves a related problem in lock-free algorithms, the ABA problem. Another approach is to just never free memory, or not free it until the structure itself is freed (when you can guarantee that no thread is using the structure anymore). I believe that this problem is one of the biggest reasons lock-free algorithms aren't more practical. I wrote more about this (and some of the weaknesses of hazard pointers) here: https://news.ycombinator.com/item?id=8265803 https://news.ycombinator.com/item?id=8265803
- wrl 12y agoConcurrencyKit[0] also has an implementation of epoch-based reclamation, which I've been experimenting with lately (with good results). [0]: http://concurrencykit.org/ http://concurrencykit.org/
- haberman 12y agoInteresting; I would like to learn more about epoch-based reclamation. It appears to require per-thread registration though?
- 12y ago
- scott_s 12y agoThe true lockfree allocators, NBMalloc, Streamflow, and the implementation of Maged Michael's alloc, all failed to compile on ALADDIN (2 failed to compile on my machine) and I don't think I should attempt to resolve that now. I'm one of the Streamflow authors and implementors. What's ALADDIN? I may be able to help get it compile.