{"article":{"slug":"freebsd-gus-rcus-cool-cousin","title":"FreeBSD GUS: RCU's cool cousin","subtitle":null,"summary":"Loïc Grégoire explains FreeBSD's GUS (global unbounded sequences), a safe memory reclamation scheme akin to RCU that was also adopted by XNU, covering why lock-free data structures need SMR and how GUS works.","content_type":"blog_post","language":"en","canonical_url":"https://gregoire.dev/writing/gus/","author":{"name":"Loïc Grégoire","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"gregoire.dev","url":null,"listing_slug":null,"listing":null},"topics":[{"name":"operating-systems","slug":"operating-systems","url":"https://listedarticles.com/topics/operating-systems"},{"name":"freebsd","slug":"freebsd","url":"https://listedarticles.com/topics/freebsd"},{"name":"concurrency","slug":"concurrency","url":"https://listedarticles.com/topics/concurrency"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":2304,"reading_minutes":10,"published_at":"2026-10-02T00:00:00.000Z","added_at":"2026-11-18T04:55:09.350Z","updated_at":"2026-11-18T04:55:09.350Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/freebsd-gus-rcus-cool-cousin","markdown_url":"https://listedarticles.com/articles/freebsd-gus-rcus-cool-cousin.md","example":false,"citation":"Loïc Grégoire, gregoire.dev. \"FreeBSD GUS: RCU's cool cousin.\" 2 Oct 2026. https://gregoire.dev/writing/gus/ (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://gregoire.dev/writing/gus/"},"body_markdown":"Writing\n2026-10-02\n\n# FreeBSD GUS\n\nRCU's cool cousin\n\n## Introduction\n\nFreeBSD has a pretty neat safe memory reclamation scheme (something akin to RCU), that's also been adopted by XNU that hasn't really been well-documented outside of code comments, and I thought it would've been interesting to write about it.\n\n## What safe memory reclamation is all about\n\nThe problem of *safe memory reclamation* (SMR) shows up notably when working with lock-free data structures. Lock-free data structures are the bread and butter of modern scalability in operating systems, and they often allow much higher throughput than their finely grained locked counterparts, but they come with their own issues.\n\nLock-free data structure code in unmanaged languages needs to carefully manage the liveness of the objects it manages, i.e it must guarantee that memory is freed if and only if no one is able to access it. This arises because there is no synchronization around the access of the data structure, so an object that is removed can still be visible concurrently by another CPU (who might have made a local copy).\n\nMore broadly, SMR schemes can also be used for other things than memory reclamation, I like to think of them as providing barriers ensuring that all participants (read: CPUs or threads) have passed through a certain point.\n\n## Prior art\n\nSMR schemes broadly fall in two families: *Epoch-based reclamation* (EBR) and *Quiescent-state based reclamation* (QSBR). You might have also heard of *Hazard Pointers* (HP), which are useful on their own but are seldom seen in operating systems (at least, that I know of!).\n\nQSBR is notable because you might've heard of it called a different name by the Linux project, *RCU* (Read-Copy-Update)! RCU's author, Paul McKenney, actually invented QSBR for the DYNIX operating system.\n\nRCU has been described extensively, and I would recommend reading McKenney's excellent [LWN Articles](https://lwn.net/Articles/262464/) to learn more. The TL;DR is that there are three operations: `rcu_read_lock`, `rcu_read_unlock` and `rcu_synchronize`, the `read` operations are used to guard reads around potentially-freed memory (i.e to enter a *read section*) and the `synchronize` function waits until there is no CPU in a read section (this could be used to wait until memory is safe to be freed).\n\nThe gist of the algorithm is that memory is known to be safe to free when all CPUs have gone through at least one *quiescent point* ever since the object was removed from its data structure (a *grace period*), and read section operations block those quiescent points from ever happening.\n\nIn practice, this can be implemented by having a quiescent point on context switches and inhibiting preemption during read operations. The core of the algorithm is actually pretty simple, and much of the complexity of the Linux code stems from making this scalable (Tree RCU) and handling other RCU flavors (e.g preemptible RCU).\n\nFreeBSD's safe memory reclamation scheme is called *GUS* and is part of the EBR family.\n\n## Epoch-based reclamation\n\nEpoch-based reclamation was first described by Keir Fraser in his now-famous thesis titled *Practical Lock-freedom* ([link](https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf)). The way it works is that there is a global *epoch* which moves through 0, 1 and 2. When a thread enters a read section, it pins itself by reading the global epoch and copying it into its local slot.\n\nWhen a writer retires an object, it goes into a \"limbo\" bag tagged with the current epoch (really, the epoch is used as an index into an array of three linked lists). The global epoch is advanced by *polling* all other threads and checking whether or not they have acknowledged the current epoch by reading their local slot; if it so happens that they have, then the global epoch is advanced and memory that was retired two epochs ago can now be freed.\n\nThe main issues that arise:\n\n1. Epochs are *bounded*, i.e they always cycle through 0, 1 and 2, this means that writers have to synchronize with epoch advancement before retiring more objects; and\n2. Doing an O(n) scan touching remote memory is very expensive!\n\nIt is now time to reveal that GUS really means *Global Unbounded Sequences*, and it tackles on issue #1 by making epochs unbounded (hence the name) and issue #2 is somewhat mitigated by clever integration with the broader system.\n\n## GUS\n\n> I am using sequence and epoch interchangeably here. Confusing, I know!\n\nThe way GUS works is that there is a global, monotonically increasing write sequence, as well as a global read sequence, which represents the last minimum observed sequence across CPUs.\n\nEach CPU also keeps track of its own local sequence when it is pinned, akin to how EBR does things.\n\nThe algorithm goes as follows, in pseudocode:\n\n```\nenter():\n    store(cpu.cur_seq, load(global_write_seq, relaxed), relaxed)\n    fence(seq_cst)\n\nexit():\n    store(cpu.cur_seq, SEQ_INVALID, release)\n\nadvance():\n    fetch_add(global_write_seq, 1, release)\n\n// Returns whether a sequence `goal` is reached\npoll(goal):\n    fence(seq_cst)\n    \n    if goal <= global_read_seq:\n        // Goal already reached!\n        return true\n\n    min_seq = global_read_seq\n\n    for each cpu:\n        min_seq = min(min_seq, load(cpu.cur_seq, relaxed))\n\n    if goal <= min_seq:\n        // Goal reached across all CPUs\n        fence(acquire)\n        \n        Exchange global_read_seq with the new one.\n        return true\n        \n    return false\n```\n\n> I will not go *too* much into details about the atomic operations here, if you're curious, they have been extensively described by people smarter than me! The basic idea, however, is that one needs to remember that all operations after `enter` must not be reordered w.r.t the publication of the epoch (the store to `cur_seq`)\n\nThe basic idea is therefore that a sequence is essentially a timestamp[[1]](https://gregoire.dev/writing/gus/#fn-1), and that the read sequence is always playing catch-up with the write sequence, but never actually reaching it,\n(i.e there is always at least a separation of 1 between both). Obviously, in practice, there is a bit more to it especially w.r.t memory orderings, but the whole thing is still freakishingly simple\nand can be implemented in a few hundred lines, see the FreeBSD implementation [here](https://elixir.bootlin.com/freebsd/v15.1/source/sys/kern/subr_smr.c).\n\nThe unbounded epochs solved the issue #1 that was presented earlier, but what about issue #2: how is polling amortized?\n\nJeff Roberson, the author of GUS, also wrote the UMA (universal memory allocator) implementation, and both tie nicely together.\n\n## Integration with the rest of the system\n\nTo me, the way GUS is integrated with the allocator is really its distinguishing feature and what makes the whole thing work well.\n\nThe UMA allocator is essentially a modernized slab allocator, which was first implemented in Solaris and described in Jeff Bonwick's influential papers[[2]](https://gregoire.dev/writing/gus/#fn-2)[[3]](https://gregoire.dev/writing/gus/#fn-3) in the early 2000s.\nTo make things scale on SMP systems, it relies on per-CPU \"buckets\" (magazines in Bonwickspeak), which are essentially an array of *N* objects on which objects are popped from and pushed onto quickly.\nA certain amount of pre-allocated buckets are stored in a per-zone (`kmem_cache` in Bonwickspeak) \"depot\" from which empty buckets and full buckets are pulled. *N*, i.e the size of buckets, is dynamically resized\naccording to measured contention on the depot lock; high contention needs to be reduced by increasing the bucket size,\nwhich provides amortization over the (potentially) slow and contended operation of going to the depot.\n\nGUS and the allocator join together by allowing the creation of \"SMR zones\" which are zones that do careful handling around the freeing of objects.\nSomeone wanting to write a lock-free data structure could create a SMR zone for their object and do allocations and frees effectively transparently.\n\nOn SMR zones, when the allocator notices a bucket is completely free (i.e full of objects), it advances the write sequence and stamps the bucket with it,\nthen puts it back at the end of the depot free list.\n\nWhen the allocator then needs to get a free bucket from the depot, it gets the bucket from the head of the free list,\nand **then** polls other CPUs for the sequence that is stamped on that bucket. If the goal has already been reached, then the bucket can be reused, otherwise,\nthe allocator will fallback on allocating another bucket itself.\n\n![](https://gregoire.dev/zone-depot.svg)\n\nDiagram of the zone depot\n\nWhat's cool about this is that buckets naturally provide amortization for those SMR operations;\npolling is done on a batch of objects at once, and not on a per-object basis (which avoids starting one write sequence per object) and growing the buckets lengthens the time spent before touching the depot again, which gives the time for other buckets to age.\n\nRemember that the GUS algorithm relies on finding the lowest sequence across all CPUs, which means that oftentimes, if buckets are aged as expected,\nthen a single poll operation could allow the reuse of many buckets at the same time, e.g if the depot free list contains buckets stamped with `100, 101, 102` and we notice via polling that the new minimum sequence is `103`,\nthen all of those buckets can be reused immediately, which avoids having to do future polls for those buckets.\n\nThat is what makes everything click together and the polling not so bad anymore!\n\n## XNU\n\nApple's XNU has also adopted a very similar scheme but with many goodies on top. For instance, they support preemptible read sections and a `call_rcu`-style API.\nThe way it integrates with their zone allocator, however, is quite interesting and its implementation differs enough that I deem it worthy to be described here as well.\n\nXNU's zone allocator (`zalloc`) is, like UMA, also essentially a modernized slab allocator;\nI will not try to explain it in depth here because it is quite sophisticated (over 10k lines!), and I am keeping this in reserve for another post, but I will go over the details of how their buckets are reused.\n\nWhat's interesting is that zalloc does not rely on resizing buckets at all, instead, buckets are kept at a fixed size (something like 8 objects),\nand a per-CPU depot is installed on top of the per-zone depot, which they call the \"recirculation depot\" (this should make sense later why such a name was used).\nThis per-CPU depot is then resized with an algorithm similar to the one used to resize buckets, providing the same kind of amortization.\n\nWhen a bucket becomes full and ready to be recycled, it is stamped with a *deferred* advance of the write sequence and put onto the per-CPU depot.\nWhen allocation is in need of a bucket, it polls the head of the per-CPU depot, and grabs it if it has expired. Otherwise, it does four things:\n\n1. **Append all the buckets from the per-CPU depot to the zone depot**\n\nSince the head of the per-CPU depot hasn't expired yet, this means that all buckets that sit in the per-CPU depot are not yet ready.\nAll buckets are therefore put at the *end* of the zone depot, as to let them age behind the buckets that were already in depot.\n\n2. **Commit the sequence of the last bucket in the zone depot**\n\nThe last bucket in the depot is the newest, its sequence is taken and the global write sequence is advanced to that one immediately,\nthis allows to do one write sequence write for many buckets.\n\n3. **Pull back a bunch of buckets from the head of zone depot into the per-CPU depot**\n\nA batch of buckets is then pulled from the head of the zone depot, these are the oldest buckets, so they are more likely to have expired.\nThe batching here avoids having to constantly thrash on the depot and avoids contention on it.\n\n4. **Retry to allocate from per-CPU depot**\n\nFinally, the oldest bucket we just freshly pulled from the zone depot is polled again, if it still hasn't expired, then\nthere is no choice but to fallback on allocating new memory.\n\nWhat's all this jazz about deferring and committing? I like to think of a deferred advance as a \"fake advance\", it snapshots the current sequence but does not increment it,\nwhich avoids a global read-modify-write (RMW) operation on the global write sequence. The key idea is that there is no need to advance the sequence, i.e commit it, until we actually need to, and\nthis also serves as an amortization feature because a sequence can be jumped to instantly, for instance, from 1 to 5 instead of individually advancing through 1, 2, 3, 4, and 5.\n\nThe recirculation depot is hence called as such because it allows a given bucket to *recirculate* and age before given the chance to be reused again.\n\n![](https://gregoire.dev/recirc-depot.svg)\n\nDiagram of the recirculation depot\n\n## Pros & Cons\n\nThis SMR scheme, like anything else, has its own tradeoffs.\nIt is relevant to compare it with RCU because both are analogous, compared to RCU:\n\nPros:\n\n- Only CPUs actively in a read-section need to participate during polling.\n- Simple implementation\n- Lower free-to-reuse latency[[4]](https://gregoire.dev/writing/gus/#fn-4)\n\nCons:\n\n- Even though polling is amortized, it is still an expensive operation, and might even be a no-go on large NUMA systems.\n- Higher overhead on entering read sections (needs a fence)\n\n## Resources\n\nThe best resource, as always, is reading the actual code, which is thankfully very well commented ([GUS link](https://elixir.bootlin.com/freebsd/v15.1/source/sys/kern/subr_smr.c), [UMA link](https://elixir.bootlin.com/freebsd/v15.1/source/sys/vm/uma_core.c)).\nThe XNU code is also heavily commented ([SMR link](https://github.com/apple-oss-distributions/xnu/blob/main/osfmk/kern/smr.c), [zalloc link](https://github.com/apple-oss-distributions/xnu/blob/main/osfmk/kern/zalloc.c)).\n\nAdditionally, these are useful resources:\n\n- Jeff Roberson has made a short [talk](https://www.youtube.com/watch?v=ZXUIFj4nRjk) about GUS and UMA.\n- Comparison with RCU by [Joel Fernandes](https://people.kernel.org/joelfernandes/gus-vs-rcu), a Linux developer.\n\nI have also implemented GUS and an allocator inspired by XNU's and UMA in my own operating system, zag ([SMR link](https://github.com/rdmsr/zag/blob/master/src/sys/kern/smr.zig), [allocator link](https://github.com/rdmsr/zag/blob/master/src/sys/mm/zone.zig))\n\n## Footnotes\n\n1. In fact, one could use a timestamp counter such as the TSC for this, as seen in [*Parallel Sequences*](https://faculty.cs.gwu.edu/gparmer/publications/eurosys16ps.pdf). [↩](https://gregoire.dev/writing/gus/#fr-1-1)\n2. [*The Slab Allocator: An Object-Caching Kernel Memory Allocator*](https://people.eecs.berkeley.edu/~kubitron/courses/cs194-24-S14/hand-outs/bonwick_slab.pdf) [↩](https://gregoire.dev/writing/gus/#fr-2-1)\n3. [*Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources*](http://www.parrot.org/sites/www.parrot.org/files/vmem.pdf) [↩](https://gregoire.dev/writing/gus/#fr-3-1)\n4. This was actually measured by the FreeBSD people, see the talk I mentioned above. [↩](https://gregoire.dev/writing/gus/#fr-4-1)\n\n© Loïc Grégoire 2026\n[CC BY 4.0](https://creativecommons.org/licenses/by/4.0/)\n","body_html":"<p>Writing\n2026-10-02</p>\n<h1 id=\"freebsd-gus\">FreeBSD GUS</h1>\n<p>RCU&#39;s cool cousin</p>\n<h2 id=\"introduction\">Introduction</h2>\n<p>FreeBSD has a pretty neat safe memory reclamation scheme (something akin to RCU), that&#39;s also been adopted by XNU that hasn&#39;t really been well-documented outside of code comments, and I thought it would&#39;ve been interesting to write about it.</p>\n<h2 id=\"what-safe-memory-reclamation-is-all-about\">What safe memory reclamation is all about</h2>\n<p>The problem of <em>safe memory reclamation</em> (SMR) shows up notably when working with lock-free data structures. Lock-free data structures are the bread and butter of modern scalability in operating systems, and they often allow much higher throughput than their finely grained locked counterparts, but they come with their own issues.</p>\n<p>Lock-free data structure code in unmanaged languages needs to carefully manage the liveness of the objects it manages, i.e it must guarantee that memory is freed if and only if no one is able to access it. This arises because there is no synchronization around the access of the data structure, so an object that is removed can still be visible concurrently by another CPU (who might have made a local copy).</p>\n<p>More broadly, SMR schemes can also be used for other things than memory reclamation, I like to think of them as providing barriers ensuring that all participants (read: CPUs or threads) have passed through a certain point.</p>\n<h2 id=\"prior-art\">Prior art</h2>\n<p>SMR schemes broadly fall in two families: <em>Epoch-based reclamation</em> (EBR) and <em>Quiescent-state based reclamation</em> (QSBR). You might have also heard of <em>Hazard Pointers</em> (HP), which are useful on their own but are seldom seen in operating systems (at least, that I know of!).</p>\n<p>QSBR is notable because you might&#39;ve heard of it called a different name by the Linux project, <em>RCU</em> (Read-Copy-Update)! RCU&#39;s author, Paul McKenney, actually invented QSBR for the DYNIX operating system.</p>\n<p>RCU has been described extensively, and I would recommend reading McKenney&#39;s excellent <a href=\"https://lwn.net/Articles/262464/\" rel=\"nofollow ugc noopener\">LWN Articles</a> to learn more. The TL;DR is that there are three operations: <code>rcu_read_lock</code>, <code>rcu_read_unlock</code> and <code>rcu_synchronize</code>, the <code>read</code> operations are used to guard reads around potentially-freed memory (i.e to enter a <em>read section</em>) and the <code>synchronize</code> function waits until there is no CPU in a read section (this could be used to wait until memory is safe to be freed).</p>\n<p>The gist of the algorithm is that memory is known to be safe to free when all CPUs have gone through at least one <em>quiescent point</em> ever since the object was removed from its data structure (a <em>grace period</em>), and read section operations block those quiescent points from ever happening.</p>\n<p>In practice, this can be implemented by having a quiescent point on context switches and inhibiting preemption during read operations. The core of the algorithm is actually pretty simple, and much of the complexity of the Linux code stems from making this scalable (Tree RCU) and handling other RCU flavors (e.g preemptible RCU).</p>\n<p>FreeBSD&#39;s safe memory reclamation scheme is called <em>GUS</em> and is part of the EBR family.</p>\n<h2 id=\"epoch-based-reclamation\">Epoch-based reclamation</h2>\n<p>Epoch-based reclamation was first described by Keir Fraser in his now-famous thesis titled <em>Practical Lock-freedom</em> (<a href=\"https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf\" rel=\"nofollow ugc noopener\">link</a>). The way it works is that there is a global <em>epoch</em> which moves through 0, 1 and 2. When a thread enters a read section, it pins itself by reading the global epoch and copying it into its local slot.</p>\n<p>When a writer retires an object, it goes into a &quot;limbo&quot; bag tagged with the current epoch (really, the epoch is used as an index into an array of three linked lists). The global epoch is advanced by <em>polling</em> all other threads and checking whether or not they have acknowledged the current epoch by reading their local slot; if it so happens that they have, then the global epoch is advanced and memory that was retired two epochs ago can now be freed.</p>\n<p>The main issues that arise:</p>\n<ol><li>Epochs are <em>bounded</em>, i.e they always cycle through 0, 1 and 2, this means that writers have to synchronize with epoch advancement before retiring more objects; and</li><li>Doing an O(n) scan touching remote memory is very expensive!</li></ol>\n<p>It is now time to reveal that GUS really means <em>Global Unbounded Sequences</em>, and it tackles on issue #1 by making epochs unbounded (hence the name) and issue #2 is somewhat mitigated by clever integration with the broader system.</p>\n<h2 id=\"gus\">GUS</h2>\n<blockquote><p>I am using sequence and epoch interchangeably here. Confusing, I know!</p></blockquote>\n<p>The way GUS works is that there is a global, monotonically increasing write sequence, as well as a global read sequence, which represents the last minimum observed sequence across CPUs.</p>\n<p>Each CPU also keeps track of its own local sequence when it is pinned, akin to how EBR does things.</p>\n<p>The algorithm goes as follows, in pseudocode:</p>\n<pre><code>enter():\n    store(cpu.cur_seq, load(global_write_seq, relaxed), relaxed)\n    fence(seq_cst)\n\nexit():\n    store(cpu.cur_seq, SEQ_INVALID, release)\n\nadvance():\n    fetch_add(global_write_seq, 1, release)\n\n// Returns whether a sequence `goal` is reached\npoll(goal):\n    fence(seq_cst)\n    \n    if goal &lt;= global_read_seq:\n        // Goal already reached!\n        return true\n\n    min_seq = global_read_seq\n\n    for each cpu:\n        min_seq = min(min_seq, load(cpu.cur_seq, relaxed))\n\n    if goal &lt;= min_seq:\n        // Goal reached across all CPUs\n        fence(acquire)\n        \n        Exchange global_read_seq with the new one.\n        return true\n        \n    return false</code></pre>\n<blockquote><p>I will not go <em>too</em> much into details about the atomic operations here, if you&#39;re curious, they have been extensively described by people smarter than me! The basic idea, however, is that one needs to remember that all operations after <code>enter</code> must not be reordered w.r.t the publication of the epoch (the store to <code>cur_seq</code>)</p></blockquote>\n<p>The basic idea is therefore that a sequence is essentially a timestamp<a href=\"https://gregoire.dev/writing/gus/#fn-1\" rel=\"nofollow ugc noopener\">[1]</a>, and that the read sequence is always playing catch-up with the write sequence, but never actually reaching it,\n(i.e there is always at least a separation of 1 between both). Obviously, in practice, there is a bit more to it especially w.r.t memory orderings, but the whole thing is still freakishingly simple\nand can be implemented in a few hundred lines, see the FreeBSD implementation <a href=\"https://elixir.bootlin.com/freebsd/v15.1/source/sys/kern/subr_smr.c\" rel=\"nofollow ugc noopener\">here</a>.</p>\n<p>The unbounded epochs solved the issue #1 that was presented earlier, but what about issue #2: how is polling amortized?</p>\n<p>Jeff Roberson, the author of GUS, also wrote the UMA (universal memory allocator) implementation, and both tie nicely together.</p>\n<h2 id=\"integration-with-the-rest-of-the-system\">Integration with the rest of the system</h2>\n<p>To me, the way GUS is integrated with the allocator is really its distinguishing feature and what makes the whole thing work well.</p>\n<p>The UMA allocator is essentially a modernized slab allocator, which was first implemented in Solaris and described in Jeff Bonwick&#39;s influential papers<a href=\"https://gregoire.dev/writing/gus/#fn-2\" rel=\"nofollow ugc noopener\">[2]</a><a href=\"https://gregoire.dev/writing/gus/#fn-3\" rel=\"nofollow ugc noopener\">[3]</a> in the early 2000s.\nTo make things scale on SMP systems, it relies on per-CPU &quot;buckets&quot; (magazines in Bonwickspeak), which are essentially an array of *N* objects on which objects are popped from and pushed onto quickly.\nA certain amount of pre-allocated buckets are stored in a per-zone (<code>kmem_cache</code> in Bonwickspeak) &quot;depot&quot; from which empty buckets and full buckets are pulled. *N*, i.e the size of buckets, is dynamically resized\naccording to measured contention on the depot lock; high contention needs to be reduced by increasing the bucket size,\nwhich provides amortization over the (potentially) slow and contended operation of going to the depot.</p>\n<p>GUS and the allocator join together by allowing the creation of &quot;SMR zones&quot; which are zones that do careful handling around the freeing of objects.\nSomeone wanting to write a lock-free data structure could create a SMR zone for their object and do allocations and frees effectively transparently.</p>\n<p>On SMR zones, when the allocator notices a bucket is completely free (i.e full of objects), it advances the write sequence and stamps the bucket with it,\nthen puts it back at the end of the depot free list.</p>\n<p>When the allocator then needs to get a free bucket from the depot, it gets the bucket from the head of the free list,\nand <strong>then</strong> polls other CPUs for the sequence that is stamped on that bucket. If the goal has already been reached, then the bucket can be reused, otherwise,\nthe allocator will fallback on allocating another bucket itself.</p>\n<figure><img src=\"https://gregoire.dev/zone-depot.svg\" alt=\"\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Diagram of the zone depot</p>\n<p>What&#39;s cool about this is that buckets naturally provide amortization for those SMR operations;\npolling is done on a batch of objects at once, and not on a per-object basis (which avoids starting one write sequence per object) and growing the buckets lengthens the time spent before touching the depot again, which gives the time for other buckets to age.</p>\n<p>Remember that the GUS algorithm relies on finding the lowest sequence across all CPUs, which means that oftentimes, if buckets are aged as expected,\nthen a single poll operation could allow the reuse of many buckets at the same time, e.g if the depot free list contains buckets stamped with <code>100, 101, 102</code> and we notice via polling that the new minimum sequence is <code>103</code>,\nthen all of those buckets can be reused immediately, which avoids having to do future polls for those buckets.</p>\n<p>That is what makes everything click together and the polling not so bad anymore!</p>\n<h2 id=\"xnu\">XNU</h2>\n<p>Apple&#39;s XNU has also adopted a very similar scheme but with many goodies on top. For instance, they support preemptible read sections and a <code>call_rcu</code>-style API.\nThe way it integrates with their zone allocator, however, is quite interesting and its implementation differs enough that I deem it worthy to be described here as well.</p>\n<p>XNU&#39;s zone allocator (<code>zalloc</code>) is, like UMA, also essentially a modernized slab allocator;\nI will not try to explain it in depth here because it is quite sophisticated (over 10k lines!), and I am keeping this in reserve for another post, but I will go over the details of how their buckets are reused.</p>\n<p>What&#39;s interesting is that zalloc does not rely on resizing buckets at all, instead, buckets are kept at a fixed size (something like 8 objects),\nand a per-CPU depot is installed on top of the per-zone depot, which they call the &quot;recirculation depot&quot; (this should make sense later why such a name was used).\nThis per-CPU depot is then resized with an algorithm similar to the one used to resize buckets, providing the same kind of amortization.</p>\n<p>When a bucket becomes full and ready to be recycled, it is stamped with a <em>deferred</em> advance of the write sequence and put onto the per-CPU depot.\nWhen allocation is in need of a bucket, it polls the head of the per-CPU depot, and grabs it if it has expired. Otherwise, it does four things:</p>\n<ol><li><strong>Append all the buckets from the per-CPU depot to the zone depot</strong></li></ol>\n<p>Since the head of the per-CPU depot hasn&#39;t expired yet, this means that all buckets that sit in the per-CPU depot are not yet ready.\nAll buckets are therefore put at the <em>end</em> of the zone depot, as to let them age behind the buckets that were already in depot.</p>\n<ol start=\"2\"><li><strong>Commit the sequence of the last bucket in the zone depot</strong></li></ol>\n<p>The last bucket in the depot is the newest, its sequence is taken and the global write sequence is advanced to that one immediately,\nthis allows to do one write sequence write for many buckets.</p>\n<ol start=\"3\"><li><strong>Pull back a bunch of buckets from the head of zone depot into the per-CPU depot</strong></li></ol>\n<p>A batch of buckets is then pulled from the head of the zone depot, these are the oldest buckets, so they are more likely to have expired.\nThe batching here avoids having to constantly thrash on the depot and avoids contention on it.</p>\n<ol start=\"4\"><li><strong>Retry to allocate from per-CPU depot</strong></li></ol>\n<p>Finally, the oldest bucket we just freshly pulled from the zone depot is polled again, if it still hasn&#39;t expired, then\nthere is no choice but to fallback on allocating new memory.</p>\n<p>What&#39;s all this jazz about deferring and committing? I like to think of a deferred advance as a &quot;fake advance&quot;, it snapshots the current sequence but does not increment it,\nwhich avoids a global read-modify-write (RMW) operation on the global write sequence. The key idea is that there is no need to advance the sequence, i.e commit it, until we actually need to, and\nthis also serves as an amortization feature because a sequence can be jumped to instantly, for instance, from 1 to 5 instead of individually advancing through 1, 2, 3, 4, and 5.</p>\n<p>The recirculation depot is hence called as such because it allows a given bucket to <em>recirculate</em> and age before given the chance to be reused again.</p>\n<figure><img src=\"https://gregoire.dev/recirc-depot.svg\" alt=\"\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Diagram of the recirculation depot</p>\n<h2 id=\"pros-cons\">Pros &amp; Cons</h2>\n<p>This SMR scheme, like anything else, has its own tradeoffs.\nIt is relevant to compare it with RCU because both are analogous, compared to RCU:</p>\n<p>Pros:</p>\n<ul><li>Only CPUs actively in a read-section need to participate during polling.</li><li>Simple implementation</li><li>Lower free-to-reuse latency<a href=\"https://gregoire.dev/writing/gus/#fn-4\" rel=\"nofollow ugc noopener\">[4]</a></li></ul>\n<p>Cons:</p>\n<ul><li>Even though polling is amortized, it is still an expensive operation, and might even be a no-go on large NUMA systems.</li><li>Higher overhead on entering read sections (needs a fence)</li></ul>\n<h2 id=\"resources\">Resources</h2>\n<p>The best resource, as always, is reading the actual code, which is thankfully very well commented (<a href=\"https://elixir.bootlin.com/freebsd/v15.1/source/sys/kern/subr_smr.c\" rel=\"nofollow ugc noopener\">GUS link</a>, <a href=\"https://elixir.bootlin.com/freebsd/v15.1/source/sys/vm/uma_core.c\" rel=\"nofollow ugc noopener\">UMA link</a>).\nThe XNU code is also heavily commented (<a href=\"https://github.com/apple-oss-distributions/xnu/blob/main/osfmk/kern/smr.c\" rel=\"nofollow ugc noopener\">SMR link</a>, <a href=\"https://github.com/apple-oss-distributions/xnu/blob/main/osfmk/kern/zalloc.c\" rel=\"nofollow ugc noopener\">zalloc link</a>).</p>\n<p>Additionally, these are useful resources:</p>\n<ul><li>Jeff Roberson has made a short <a href=\"https://www.youtube.com/watch?v=ZXUIFj4nRjk\" rel=\"nofollow ugc noopener\">talk</a> about GUS and UMA.</li><li>Comparison with RCU by <a href=\"https://people.kernel.org/joelfernandes/gus-vs-rcu\" rel=\"nofollow ugc noopener\">Joel Fernandes</a>, a Linux developer.</li></ul>\n<p>I have also implemented GUS and an allocator inspired by XNU&#39;s and UMA in my own operating system, zag (<a href=\"https://github.com/rdmsr/zag/blob/master/src/sys/kern/smr.zig\" rel=\"nofollow ugc noopener\">SMR link</a>, <a href=\"https://github.com/rdmsr/zag/blob/master/src/sys/mm/zone.zig\" rel=\"nofollow ugc noopener\">allocator link</a>)</p>\n<h2 id=\"footnotes\">Footnotes</h2>\n<ol><li>In fact, one could use a timestamp counter such as the TSC for this, as seen in <a href=\"https://faculty.cs.gwu.edu/gparmer/publications/eurosys16ps.pdf\" rel=\"nofollow ugc noopener\"><em>Parallel Sequences</em></a>. <a href=\"https://gregoire.dev/writing/gus/#fr-1-1\" rel=\"nofollow ugc noopener\">↩</a></li><li><a href=\"https://people.eecs.berkeley.edu/~kubitron/courses/cs194-24-S14/hand-outs/bonwick_slab.pdf\" rel=\"nofollow ugc noopener\"><em>The Slab Allocator: An Object-Caching Kernel Memory Allocator</em></a> <a href=\"https://gregoire.dev/writing/gus/#fr-2-1\" rel=\"nofollow ugc noopener\">↩</a></li><li><a href=\"http://www.parrot.org/sites/www.parrot.org/files/vmem.pdf\" rel=\"nofollow ugc noopener\"><em>Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources</em></a> <a href=\"https://gregoire.dev/writing/gus/#fr-3-1\" rel=\"nofollow ugc noopener\">↩</a></li><li>This was actually measured by the FreeBSD people, see the talk I mentioned above. <a href=\"https://gregoire.dev/writing/gus/#fr-4-1\" rel=\"nofollow ugc noopener\">↩</a></li></ol>\n<p>© Loïc Grégoire 2026\n<a href=\"https://creativecommons.org/licenses/by/4.0/\" rel=\"nofollow ugc noopener\">CC BY 4.0</a></p>","headings":[{"level":1,"text":"FreeBSD GUS","id":"freebsd-gus"},{"level":2,"text":"Introduction","id":"introduction"},{"level":2,"text":"What safe memory reclamation is all about","id":"what-safe-memory-reclamation-is-all-about"},{"level":2,"text":"Prior art","id":"prior-art"},{"level":2,"text":"Epoch-based reclamation","id":"epoch-based-reclamation"},{"level":2,"text":"GUS","id":"gus"},{"level":2,"text":"Integration with the rest of the system","id":"integration-with-the-rest-of-the-system"},{"level":2,"text":"XNU","id":"xnu"},{"level":2,"text":"Pros & Cons","id":"pros-cons"},{"level":2,"text":"Resources","id":"resources"},{"level":2,"text":"Footnotes","id":"footnotes"}]}}