{"article":{"slug":"handles-are-the-better-pointers","title":"Handles are the better pointers","subtitle":null,"summary":"Andre Weissflog (floooh) describes replacing raw and smart pointers in C and C++ with index handles: centralizing memory management in systems that own arrays of items, giving out integer handles instead of pointers, and using per-slot generation counters to detect dangling handles safely.","content_type":"blog_post","language":"en","canonical_url":"https://floooh.github.io/2018/06/17/handles-vs-pointers.html","author":{"name":"Andre Weissflog","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"The Brain Dump (floooh.github.io)","url":null,"listing_slug":null,"listing":null},"topics":[{"name":"c","slug":"c","url":"https://listedarticles.com/topics/c"},{"name":"cpp","slug":"cpp","url":"https://listedarticles.com/topics/cpp"},{"name":"memory-management","slug":"memory-management","url":"https://listedarticles.com/topics/memory-management"},{"name":"programming","slug":"programming","url":"https://listedarticles.com/topics/programming"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":2978,"reading_minutes":13,"published_at":"2018-06-17T00:00:00.000Z","added_at":"2026-11-03T17:11:48.140Z","updated_at":"2026-11-03T17:11:48.140Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/handles-are-the-better-pointers","markdown_url":"https://listedarticles.com/articles/handles-are-the-better-pointers.md","example":false,"citation":"Andre Weissflog, The Brain Dump (floooh.github.io). \"Handles are the better pointers.\" 17 Jun 2018. https://floooh.github.io/2018/06/17/handles-vs-pointers.html (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://floooh.github.io/2018/06/17/handles-vs-pointers.html"},"body_markdown":"# Handles are the better pointers\n\n*by Andre Weissflog (floooh), Jun 17, 2018*\n\n**28-Nov-2018**: I’ve added a small update at the end on how to prevent\n‘handle collisions’ with a per-slot generation counter\n\n**Original Post**:\n\n…wherein I talk a bit about how I’m doing dynamic memory management in C\nand C++ these days which basically replaces raw- and smart-pointers with\n‘index-handles’.\n\nIn my [last blog post](https://floooh.github.io/2018/06/02/one-year-of-c.html) I was mentioning\npointer- and allocation-free programming, but was skipping over\nthe details. This is what the following blog post is\nabout.\n\nThis is all based on the (sometimes painful) experience of wrestling for 15+\nyears with fairly big C++ code bases (0.5 to around 1 mloc) where memory is\noften managed through smart pointers. The worst case being tens- to\nhundreds-of-thousands of small C++ objects, each in its own heap\nallocation, pointing to each other through smart pointers. While such code\nis quite robust in terms of memory corruption (segfaults and corruption\nrarely happens, since most attempts are caught by asserts when dereferencing\nsmart pointers), this type of ‘object spiderweb code’ is also dog-slow\nwithout obvious starting points for optimization, since the entire code is full of\ncache misses. Other typical problems are memory fragmentation and ‘fake\nmemory leaks’ because a forgotten smart pointer prevents freeing the\nunderlying memory (I call them ‘fake leaks’ because this type of leaks cannot\nbe caught by memory debugging tools).\n\nNothing presented here is particularly new or clever, it’s just\na collection of a few simple ideas which together work fairly well in bigger\ncode bases to prevent (or at least detect early) a number of common\nmemory-related problems in C and C++, and may even be useful in higher-level\ngarbage-collected languages to reduce pressure on the garbage collector.\n\nHowever, the underlying design philosophy doesn’t fit very well into a\nclassical OOP world where applications are built from small autonomous\nobjects interacting with each other. That’s why it’s also quite tricky to\nimplement those ideas in a big existing OOP code base, where object creation\nand destruction happens ‘decentralized’ all over the code.\n\nThe approach described here works very well though with a data-oriented\narchitecture, where central systems work on arrays of data items packed\ntightly in memory.\n\nMost of the following blog post is written from a game developer’s\nperspective, but should also apply to other areas where a program needs to\njuggle a few hundred to a few million objects (or generally ‘data items’) in\nmemory, and where such items are created and destroyed frequently.\n\nThe gist is:\n\n- move all memory management into centralized systems (like rendering, physics, animation, …), with the systems being the sole owner of their memory allocations\n- group items of the same type into arrays, and treat the array base pointer as system-private\n- when creating an item, only return an ‘index-handle’ to the outside world, not a pointer to the item\n- in the index-handles, only use as many bits as needed for the array index, and use the remaining bits for additional memory safety checks\n- only convert a handle to a pointer when absolutely needed, and don’t store the pointer anywhere\n\nI’ll explain each of those points in detail below. But the idea is basically\nthat common ‘user-level’ code doesn’t directly call memory allocation\nfunctions (like malloc, new or make\\_shared/make\\_unique), and reduces the use\nof pointers to an absolute minimum (only as short-lived references when\ndirect memory access to an item is absolutely needed). Most importantly,\npointers are never the ‘owner’ of an item’s underlying memory.\n\nInstead, direct memory manipulation happens as much as possible inside a few\ncentralized systems where memory-related problems are easier to debug and\noptimize.\n\n## Move memory management into central systems\n\nIn this blog post, a ‘system’ is a (usually fairly big) part of a code base\nwhich takes care of a number of related tasks, like ‘rendering’, ‘physics’,\n‘AI’, ‘character animation’ and so on. Such a system is separated from other\nsystems and ‘user-code’ through a clearly defined function API, and the work\nthat happens on the system’s data is performed in tight central loops instead\nof being spread out all over the code base.\n\nSystems often work on items created and destroyed under control of user code\n(but note that creation and destruction of items is different from allocating\nand freeing the memory used by those items!). For instance a rendering system\nmight deal with vertex buffers, textures, shaders and pipeline state objects.\nA physics system works with rigid bodies, joints and collision primitives,\nand an animation system works with animation keys and curves.\n\nIt makes sense to move the memory management for such items into the systems\nthemselves, because a general memory allocator doesn’t have the\nsystem-specific ‘domain knowledge’ about how data items are processed and the\nrelationships between data items. This allows the system to optimize memory\nallocations, perform additional validation checks when creating and\ndestroying items, and arrange items in memory for making best use of the\nCPU’s data caches.\n\nA good example for this ‘system domain knowledge’ is the destruction of\nrendering resource objects with modern 3D APIs: a resource object can not\nsimply be destroyed immediately when the user code says so because the\nresource might still be referenced in a command list waiting to be consumed\nby the GPU. Instead the rendering system would only mark the resource object\nfor destruction when the user code requests its destruction, but the actual\ndestruction happens at a later time when the GPU no longer uses the resource.\n\n## Group items of the same type into arrays\n\nOnce all memory management has moved into systems, the system can optimize\nmemory allocations and memory layout with its additional knowledge about how\nitems are used. One obvious optimization is to reduce the number of general\nmemory allocations by grouping items of the same type into arrays, and\nallocate those arrays at system startup.\n\nInstead of performing a memory allocation each time a new item is created,\nthe system keeps track of free array slots, and picks the next free slot.\nWhen the user code no longer needs the item, the system simply marks the slot\nas free again instead of performing a deallocation (not different\nfrom a typical pool allocator).\n\nThis pool allocation is most likely a little bit faster than performing a\nmemory allocation per item, but this is not even the main reason for keeping\nitems in arrays (modern general allocators are quite fast too for small\nallocations).\n\nA few additional advantages are:\n\n- items are guaranteed to be packed tightly in memory, general allocators sometimes need to keep some housekeeping data next to the actual item memory\n- it’s easier to keep ‘hot items’ in continuous memory ranges, so that the CPU can make better use of its data caches\n- it’s also possible to split the data of a single item into several subitems in different arrays for even tighter packing and better data cache usage (AoS vs SoA and everything inbetween), and all those data layout details remain private to the system and are trivial to change without affecting ‘outside code’\n- as long as the system doesn’t need to reallocate arrays, it is guaranteed that there will be no memory fragmentation (although this is less of an issue in a 64-bit address space)\n- it’s easier to detect memory leaks early, and provide more useful error messages: when a new item is created a system can trivially check the current number of items against an expected upper bound (for instance a game might know that there should never be more than 1024 textures alive at a time, and since all textures are created through the rendering system, the system can print out a more useful warning message when this number is exceeded)\n\n## Public index-handles instead of pointers\n\nKeeping system items in arrays instead of unique allocations has the\nadvantage that an item can be identified through an array index instead of\nrequiring a full pointer. This is very useful for memory safety.\nInstead of handing memory pointers to the outside world, the system can treat\nthe array base pointers as ‘private knowledge’, and only hand out array\nindices to the public. Without the base pointer to compute an item’s memory\nlocation, the outside code can’t access the item’s memory, even with a lot\nof criminal energy.\n\nThis has a number of further advantages:\n\n- In many situations, code outside the system never even needs to directly access memory of an item, only the system does. In such an ‘ideal’ situation, user code never accesses memory through pointers, and can never cause memory corruption.\n- Since only the system knows the array base pointers, it’s free to move or reallocate the item arrays at will without invalidating existing index handles.\n- Array indices need fewer bits than full pointers, and a smaller data type can be picked for them, which in turn allows tighter packing of data structures and better data cache usage (this has the caveat that additional handle bits can be used to increase memory safety, more about this below)\n\nIf user code needs to access the memory of an item directly it needs to obtain\na pointer through a ‘lookup function’ which takes a handle as input and returns\na pointer. As soon as such a lookup function exists, the fairly watertight\nmemory safety scenario outlined above is no longer guaranteed, and the user code\nshould adhere to a few rules:\n\n- pointers should never be stored anywhere, since the next time the pointer is used it may no longer point to the same item, or even to valid memory\n- a pointer should only be used in a simple code block, and not ‘across’ function calls\n\nEvery time a handle is converted into a pointer, the system can guarantee\nthat the returned pointer still points to the same item that the handle was\noriginally created for (more on this below), but this guarantee ‘decays’ over\ntime since the item under the pointer may have been destroyed, or the underlying\nmemory may have been reallocated to a different location (this is the same\nproblem as iterator invalidation in C++).\n\nThe two simple rules above are easy to memorize and are a good compromise between\nnot exposing pointers to user code at all, and having a (somewhat costly)\nhandle-to-pointer conversion for every single memory access.\n\n## Memory safety considerations\n\nFirst, each type of handle should get its own C/C++ type, so that attempting\nto pass the wrong handle type to a function is already detected at compile\ntime (note that a simple typedef isn’t enough to produce a compiler warning,\nthe handle must be wrapped into its own struct or class - however this could\nbe limited to debug compilation mode).\n\nAll runtime memory safety checks happen in the function which converts a\nhandle into a pointer. If the handle is just an array index, it would look\nlike this:\n\n- a range check happens for the index against the current item array size, this prevents segmentation faults and reading or writing allocated but unrelated memory areas\n- a check needs to happen whether the indexed array item slot contains an active item (is not currently a ‘free slot’), this prevents the simple variant of ‘use after free’\n- finally the item pointer is computed from the private array base pointer and public item index\n\nThe resulting pointer is safe to use as long as:\n\n- the item array isn’t reallocated\n- the indexed item hasn’t been destroyed\n\nBoth can only happen inside one of the system’s functions, that’s why the two\n‘pointer usage rules’ exist (don’t store pointers, don’t keep pointers across\nfunction calls).\n\nThere is a pretty big hole in the above use-after-free check though: if we only\ncheck if an array slot behind an index-handle contains a valid item, it’s\nnot guaranteed that it is the *same* item the handle was originally created\nfor. It can happen that the original item was destroyed, and the same\narray slot was reused for a *new* item.\n\nThis is where the ‘free bits’ in a handle come in: Let’s say our\nhandles are 16-bits, but we only ever need 1024 items alive\nat the same time. Only 10 index bits are needed to address 1024 items, which\nleaves 6 bits free for something else.\n\nIf those 6 bits contain some sort of ‘unique pattern’, it’s possible to\ndetect dangling accesses:\n\n- When an item is created, a free array item is picked and its index is put into the lower 10 handle bits. The upper 6 bits are set to a ‘unique bit pattern’\n- The resulting 16-bit handle (10 bits index + 6 bit ‘unique pattern’) are returned to the outside world, and at the same time stored with the array slot.\n- When an item is destroyed, the item handle stored with the array slot is set to the ‘invalid handle’ value (can be zero, as long as zero is never returned as a valid handle to the outside world)\n- When the handle is converted to a pointer, the lower 10 bits are used as array index to lookup the array slot, and the entire 16-bit handle is compared against the handle that’s currently stored with the array slot:\n  - if both handles are equal, the pointer is valid and points to the same item the handle was created for\n  - otherwise this is a dangling access, the slot item has either been destroyed (in that case the stored handle would have the ‘invalid handle’ value), or has been destroyed and reused for a new item (in that case the upper 6 ‘unique pattern’ bits don’t match)\n\nThis handle-comparison check when converting a handle to a pointer works\nquite well to detect dangling-accesses, but it isn’t waterproof because the\nsame combination of array index and ‘unique pattern’ will be created sooner or\nlater.\nBut it’s still better than no dangling protection at all (like raw pointers),\nor a ‘fake memory leak’ which would happen in similar situations with smart pointers.\n\nFinding good strategies to create unique handles that collide as rarely as\npossible is the most important part of course, and left as an excercise to\nthe reader ;P\n\nObviously it’s good to use as many bits for the unique pattern as possible, and the\nway how free array slots are reused is important as well (e.g. LIFO vs FIFO). It’s\nprobably also good to write a little creation/destruction stress-test which\nchecks for handle collisions and can be used to tweak the unique-pattern creation for\nspecific use cases. A system where items are created and destroyed with a very\nhigh frequency needs more effort (or simply more handle bits) than systems\nwhere item creation and destruction is a rare occurance.\n\n## Other useful properties of handles\n\nApart from the whole memory safety aspect, handles are also useful for other\nsituations where pointers are problematic:\n\nHandles can be used as shared object identifiers across processes (all you need is\nsome sort of ‘create\\_item\\_with\\_handle()’ function, which doesn’t create a\nnew handle, but takes an existing handle as input argument). This is especially\nuseful for online games where handles can be shared between the server and\nall clients in a game session, or in savegame systems to store references\nto other objects.\n\nSometimes it’s useful to create a whole group of related items (for instance\nanimation keys and curves), and reference the whole item group with a single\nhandle. In that case some sort of ‘range handle’ can be used, which contains\nnot only an index (of the first item), but also the number of items in the range.\n\nIn some situations it’s also useful to reserve a few handle bits for an item\ntype if static type checking at compile time isn’t sufficient.\n\nIn conclusion, I find it quite surprising how naturally and elegantly handles\nsolve many problems I encountered in the past with the traditional ‘pointers\nto objects on the heap’ model, and how little I miss this model now (and the\nparts of C++ that are built around it).\n\n## Some real-world examples\n\nThe sokol-gfx API is an example of a C-API which uses handles instead of\npointer of rendering resource objects (buffers, images, shaders, …):\n\n**[sokol\\_gfx.h](https://github.com/floooh/sokol#sokol_gfxh)**\n\nThe Oryol Gfx module is a similar 3D API wrapper, but written in C++:\n\n**[Oryol Gfx Module](https://github.com/floooh/oryol/tree/sokol-gfx/code/Modules/Gfx)**\n\nThe Oryol Animation extension module is a character animation system which keeps all its data in arrays:\n\n**[Oryol Anim Module](https://github.com/floooh/oryol-animation/tree/master/src/Anim)**\n\n## Update 28-Nov-2018\n\n…in the post above I was sort of handwaving away the problem of creating\nthe same unique-tag twice for the same slot, and a nice person on twitter\nhinted me about a very simple, elegant and embarrassingly ‘obvious’ solution:\n\nEach array slot gets its own **generation counter**, which is bumped when a\nhandle is released (can also happen when the handle is created, but bumping\non release means you don’t need a reserved value for “free slots” to detect\nan invalid handle).\n\nTo check if a handle is valid, simply compare its unique-tag with the current\ngeneration counter in its slot.\n\nOnce the generation counter would ‘overflow’, **disable** that array slot, so\nthat no new handles are returned for this slot.\n\nThis is a perfect solution for avoiding handle collisions, but the handles\nwill eventually run out since all array slots will be disabled eventually. But\nsince each slot has its own counter, this only happens after *all*\nhandle-bits are exhausted, not just the few unique-tag bits.\n\nSo with 32-bit handles, you can always create 4 billion items, with at most\n2^(32 - num\\_counter\\_bits) alive at the same time. This also means the number of\nbits for the unique-tag can be reduced without compromising ‘handle safety’.\n\nIt may also be possible to re-activate disabled slots once it can be\nguaranteed that no more handles for that slot are out in the wild\n(maybe at special places in the code like entering or exiting a level).\n","body_html":"<h1 id=\"handles-are-the-better-pointers\">Handles are the better pointers</h1>\n<p><em>by Andre Weissflog (floooh), Jun 17, 2018</em></p>\n<p><strong>28-Nov-2018</strong>: I’ve added a small update at the end on how to prevent\n‘handle collisions’ with a per-slot generation counter</p>\n<p><strong>Original Post</strong>:</p>\n<p>…wherein I talk a bit about how I’m doing dynamic memory management in C\nand C++ these days which basically replaces raw- and smart-pointers with\n‘index-handles’.</p>\n<p>In my <a href=\"https://floooh.github.io/2018/06/02/one-year-of-c.html\" rel=\"nofollow ugc noopener\">last blog post</a> I was mentioning\npointer- and allocation-free programming, but was skipping over\nthe details. This is what the following blog post is\nabout.</p>\n<p>This is all based on the (sometimes painful) experience of wrestling for 15+\nyears with fairly big C++ code bases (0.5 to around 1 mloc) where memory is\noften managed through smart pointers. The worst case being tens- to\nhundreds-of-thousands of small C++ objects, each in its own heap\nallocation, pointing to each other through smart pointers. While such code\nis quite robust in terms of memory corruption (segfaults and corruption\nrarely happens, since most attempts are caught by asserts when dereferencing\nsmart pointers), this type of ‘object spiderweb code’ is also dog-slow\nwithout obvious starting points for optimization, since the entire code is full of\ncache misses. Other typical problems are memory fragmentation and ‘fake\nmemory leaks’ because a forgotten smart pointer prevents freeing the\nunderlying memory (I call them ‘fake leaks’ because this type of leaks cannot\nbe caught by memory debugging tools).</p>\n<p>Nothing presented here is particularly new or clever, it’s just\na collection of a few simple ideas which together work fairly well in bigger\ncode bases to prevent (or at least detect early) a number of common\nmemory-related problems in C and C++, and may even be useful in higher-level\ngarbage-collected languages to reduce pressure on the garbage collector.</p>\n<p>However, the underlying design philosophy doesn’t fit very well into a\nclassical OOP world where applications are built from small autonomous\nobjects interacting with each other. That’s why it’s also quite tricky to\nimplement those ideas in a big existing OOP code base, where object creation\nand destruction happens ‘decentralized’ all over the code.</p>\n<p>The approach described here works very well though with a data-oriented\narchitecture, where central systems work on arrays of data items packed\ntightly in memory.</p>\n<p>Most of the following blog post is written from a game developer’s\nperspective, but should also apply to other areas where a program needs to\njuggle a few hundred to a few million objects (or generally ‘data items’) in\nmemory, and where such items are created and destroyed frequently.</p>\n<p>The gist is:</p>\n<ul><li>move all memory management into centralized systems (like rendering, physics, animation, …), with the systems being the sole owner of their memory allocations</li><li>group items of the same type into arrays, and treat the array base pointer as system-private</li><li>when creating an item, only return an ‘index-handle’ to the outside world, not a pointer to the item</li><li>in the index-handles, only use as many bits as needed for the array index, and use the remaining bits for additional memory safety checks</li><li>only convert a handle to a pointer when absolutely needed, and don’t store the pointer anywhere</li></ul>\n<p>I’ll explain each of those points in detail below. But the idea is basically\nthat common ‘user-level’ code doesn’t directly call memory allocation\nfunctions (like malloc, new or make_shared/make_unique), and reduces the use\nof pointers to an absolute minimum (only as short-lived references when\ndirect memory access to an item is absolutely needed). Most importantly,\npointers are never the ‘owner’ of an item’s underlying memory.</p>\n<p>Instead, direct memory manipulation happens as much as possible inside a few\ncentralized systems where memory-related problems are easier to debug and\noptimize.</p>\n<h2 id=\"move-memory-management-into-central-systems\">Move memory management into central systems</h2>\n<p>In this blog post, a ‘system’ is a (usually fairly big) part of a code base\nwhich takes care of a number of related tasks, like ‘rendering’, ‘physics’,\n‘AI’, ‘character animation’ and so on. Such a system is separated from other\nsystems and ‘user-code’ through a clearly defined function API, and the work\nthat happens on the system’s data is performed in tight central loops instead\nof being spread out all over the code base.</p>\n<p>Systems often work on items created and destroyed under control of user code\n(but note that creation and destruction of items is different from allocating\nand freeing the memory used by those items!). For instance a rendering system\nmight deal with vertex buffers, textures, shaders and pipeline state objects.\nA physics system works with rigid bodies, joints and collision primitives,\nand an animation system works with animation keys and curves.</p>\n<p>It makes sense to move the memory management for such items into the systems\nthemselves, because a general memory allocator doesn’t have the\nsystem-specific ‘domain knowledge’ about how data items are processed and the\nrelationships between data items. This allows the system to optimize memory\nallocations, perform additional validation checks when creating and\ndestroying items, and arrange items in memory for making best use of the\nCPU’s data caches.</p>\n<p>A good example for this ‘system domain knowledge’ is the destruction of\nrendering resource objects with modern 3D APIs: a resource object can not\nsimply be destroyed immediately when the user code says so because the\nresource might still be referenced in a command list waiting to be consumed\nby the GPU. Instead the rendering system would only mark the resource object\nfor destruction when the user code requests its destruction, but the actual\ndestruction happens at a later time when the GPU no longer uses the resource.</p>\n<h2 id=\"group-items-of-the-same-type-into-arrays\">Group items of the same type into arrays</h2>\n<p>Once all memory management has moved into systems, the system can optimize\nmemory allocations and memory layout with its additional knowledge about how\nitems are used. One obvious optimization is to reduce the number of general\nmemory allocations by grouping items of the same type into arrays, and\nallocate those arrays at system startup.</p>\n<p>Instead of performing a memory allocation each time a new item is created,\nthe system keeps track of free array slots, and picks the next free slot.\nWhen the user code no longer needs the item, the system simply marks the slot\nas free again instead of performing a deallocation (not different\nfrom a typical pool allocator).</p>\n<p>This pool allocation is most likely a little bit faster than performing a\nmemory allocation per item, but this is not even the main reason for keeping\nitems in arrays (modern general allocators are quite fast too for small\nallocations).</p>\n<p>A few additional advantages are:</p>\n<ul><li>items are guaranteed to be packed tightly in memory, general allocators sometimes need to keep some housekeeping data next to the actual item memory</li><li>it’s easier to keep ‘hot items’ in continuous memory ranges, so that the CPU can make better use of its data caches</li><li>it’s also possible to split the data of a single item into several subitems in different arrays for even tighter packing and better data cache usage (AoS vs SoA and everything inbetween), and all those data layout details remain private to the system and are trivial to change without affecting ‘outside code’</li><li>as long as the system doesn’t need to reallocate arrays, it is guaranteed that there will be no memory fragmentation (although this is less of an issue in a 64-bit address space)</li><li>it’s easier to detect memory leaks early, and provide more useful error messages: when a new item is created a system can trivially check the current number of items against an expected upper bound (for instance a game might know that there should never be more than 1024 textures alive at a time, and since all textures are created through the rendering system, the system can print out a more useful warning message when this number is exceeded)</li></ul>\n<h2 id=\"public-index-handles-instead-of-pointers\">Public index-handles instead of pointers</h2>\n<p>Keeping system items in arrays instead of unique allocations has the\nadvantage that an item can be identified through an array index instead of\nrequiring a full pointer. This is very useful for memory safety.\nInstead of handing memory pointers to the outside world, the system can treat\nthe array base pointers as ‘private knowledge’, and only hand out array\nindices to the public. Without the base pointer to compute an item’s memory\nlocation, the outside code can’t access the item’s memory, even with a lot\nof criminal energy.</p>\n<p>This has a number of further advantages:</p>\n<ul><li>In many situations, code outside the system never even needs to directly access memory of an item, only the system does. In such an ‘ideal’ situation, user code never accesses memory through pointers, and can never cause memory corruption.</li><li>Since only the system knows the array base pointers, it’s free to move or reallocate the item arrays at will without invalidating existing index handles.</li><li>Array indices need fewer bits than full pointers, and a smaller data type can be picked for them, which in turn allows tighter packing of data structures and better data cache usage (this has the caveat that additional handle bits can be used to increase memory safety, more about this below)</li></ul>\n<p>If user code needs to access the memory of an item directly it needs to obtain\na pointer through a ‘lookup function’ which takes a handle as input and returns\na pointer. As soon as such a lookup function exists, the fairly watertight\nmemory safety scenario outlined above is no longer guaranteed, and the user code\nshould adhere to a few rules:</p>\n<ul><li>pointers should never be stored anywhere, since the next time the pointer is used it may no longer point to the same item, or even to valid memory</li><li>a pointer should only be used in a simple code block, and not ‘across’ function calls</li></ul>\n<p>Every time a handle is converted into a pointer, the system can guarantee\nthat the returned pointer still points to the same item that the handle was\noriginally created for (more on this below), but this guarantee ‘decays’ over\ntime since the item under the pointer may have been destroyed, or the underlying\nmemory may have been reallocated to a different location (this is the same\nproblem as iterator invalidation in C++).</p>\n<p>The two simple rules above are easy to memorize and are a good compromise between\nnot exposing pointers to user code at all, and having a (somewhat costly)\nhandle-to-pointer conversion for every single memory access.</p>\n<h2 id=\"memory-safety-considerations\">Memory safety considerations</h2>\n<p>First, each type of handle should get its own C/C++ type, so that attempting\nto pass the wrong handle type to a function is already detected at compile\ntime (note that a simple typedef isn’t enough to produce a compiler warning,\nthe handle must be wrapped into its own struct or class - however this could\nbe limited to debug compilation mode).</p>\n<p>All runtime memory safety checks happen in the function which converts a\nhandle into a pointer. If the handle is just an array index, it would look\nlike this:</p>\n<ul><li>a range check happens for the index against the current item array size, this prevents segmentation faults and reading or writing allocated but unrelated memory areas</li><li>a check needs to happen whether the indexed array item slot contains an active item (is not currently a ‘free slot’), this prevents the simple variant of ‘use after free’</li><li>finally the item pointer is computed from the private array base pointer and public item index</li></ul>\n<p>The resulting pointer is safe to use as long as:</p>\n<ul><li>the item array isn’t reallocated</li><li>the indexed item hasn’t been destroyed</li></ul>\n<p>Both can only happen inside one of the system’s functions, that’s why the two\n‘pointer usage rules’ exist (don’t store pointers, don’t keep pointers across\nfunction calls).</p>\n<p>There is a pretty big hole in the above use-after-free check though: if we only\ncheck if an array slot behind an index-handle contains a valid item, it’s\nnot guaranteed that it is the <em>same</em> item the handle was originally created\nfor. It can happen that the original item was destroyed, and the same\narray slot was reused for a <em>new</em> item.</p>\n<p>This is where the ‘free bits’ in a handle come in: Let’s say our\nhandles are 16-bits, but we only ever need 1024 items alive\nat the same time. Only 10 index bits are needed to address 1024 items, which\nleaves 6 bits free for something else.</p>\n<p>If those 6 bits contain some sort of ‘unique pattern’, it’s possible to\ndetect dangling accesses:</p>\n<ul><li>When an item is created, a free array item is picked and its index is put into the lower 10 handle bits. The upper 6 bits are set to a ‘unique bit pattern’</li><li>The resulting 16-bit handle (10 bits index + 6 bit ‘unique pattern’) are returned to the outside world, and at the same time stored with the array slot.</li><li>When an item is destroyed, the item handle stored with the array slot is set to the ‘invalid handle’ value (can be zero, as long as zero is never returned as a valid handle to the outside world)</li><li>When the handle is converted to a pointer, the lower 10 bits are used as array index to lookup the array slot, and the entire 16-bit handle is compared against the handle that’s currently stored with the array slot:<ul><li>if both handles are equal, the pointer is valid and points to the same item the handle was created for</li><li>otherwise this is a dangling access, the slot item has either been destroyed (in that case the stored handle would have the ‘invalid handle’ value), or has been destroyed and reused for a new item (in that case the upper 6 ‘unique pattern’ bits don’t match)</li></ul></li></ul>\n<p>This handle-comparison check when converting a handle to a pointer works\nquite well to detect dangling-accesses, but it isn’t waterproof because the\nsame combination of array index and ‘unique pattern’ will be created sooner or\nlater.\nBut it’s still better than no dangling protection at all (like raw pointers),\nor a ‘fake memory leak’ which would happen in similar situations with smart pointers.</p>\n<p>Finding good strategies to create unique handles that collide as rarely as\npossible is the most important part of course, and left as an excercise to\nthe reader ;P</p>\n<p>Obviously it’s good to use as many bits for the unique pattern as possible, and the\nway how free array slots are reused is important as well (e.g. LIFO vs FIFO). It’s\nprobably also good to write a little creation/destruction stress-test which\nchecks for handle collisions and can be used to tweak the unique-pattern creation for\nspecific use cases. A system where items are created and destroyed with a very\nhigh frequency needs more effort (or simply more handle bits) than systems\nwhere item creation and destruction is a rare occurance.</p>\n<h2 id=\"other-useful-properties-of-handles\">Other useful properties of handles</h2>\n<p>Apart from the whole memory safety aspect, handles are also useful for other\nsituations where pointers are problematic:</p>\n<p>Handles can be used as shared object identifiers across processes (all you need is\nsome sort of ‘create_item_with_handle()’ function, which doesn’t create a\nnew handle, but takes an existing handle as input argument). This is especially\nuseful for online games where handles can be shared between the server and\nall clients in a game session, or in savegame systems to store references\nto other objects.</p>\n<p>Sometimes it’s useful to create a whole group of related items (for instance\nanimation keys and curves), and reference the whole item group with a single\nhandle. In that case some sort of ‘range handle’ can be used, which contains\nnot only an index (of the first item), but also the number of items in the range.</p>\n<p>In some situations it’s also useful to reserve a few handle bits for an item\ntype if static type checking at compile time isn’t sufficient.</p>\n<p>In conclusion, I find it quite surprising how naturally and elegantly handles\nsolve many problems I encountered in the past with the traditional ‘pointers\nto objects on the heap’ model, and how little I miss this model now (and the\nparts of C++ that are built around it).</p>\n<h2 id=\"some-real-world-examples\">Some real-world examples</h2>\n<p>The sokol-gfx API is an example of a C-API which uses handles instead of\npointer of rendering resource objects (buffers, images, shaders, …):</p>\n<p><strong><a href=\"https://github.com/floooh/sokol#sokol_gfxh\" rel=\"nofollow ugc noopener\">sokol_gfx.h</a></strong></p>\n<p>The Oryol Gfx module is a similar 3D API wrapper, but written in C++:</p>\n<p><strong><a href=\"https://github.com/floooh/oryol/tree/sokol-gfx/code/Modules/Gfx\" rel=\"nofollow ugc noopener\">Oryol Gfx Module</a></strong></p>\n<p>The Oryol Animation extension module is a character animation system which keeps all its data in arrays:</p>\n<p><strong><a href=\"https://github.com/floooh/oryol-animation/tree/master/src/Anim\" rel=\"nofollow ugc noopener\">Oryol Anim Module</a></strong></p>\n<h2 id=\"update-28-nov-2018\">Update 28-Nov-2018</h2>\n<p>…in the post above I was sort of handwaving away the problem of creating\nthe same unique-tag twice for the same slot, and a nice person on twitter\nhinted me about a very simple, elegant and embarrassingly ‘obvious’ solution:</p>\n<p>Each array slot gets its own <strong>generation counter</strong>, which is bumped when a\nhandle is released (can also happen when the handle is created, but bumping\non release means you don’t need a reserved value for “free slots” to detect\nan invalid handle).</p>\n<p>To check if a handle is valid, simply compare its unique-tag with the current\ngeneration counter in its slot.</p>\n<p>Once the generation counter would ‘overflow’, <strong>disable</strong> that array slot, so\nthat no new handles are returned for this slot.</p>\n<p>This is a perfect solution for avoiding handle collisions, but the handles\nwill eventually run out since all array slots will be disabled eventually. But\nsince each slot has its own counter, this only happens after <em>all</em>\nhandle-bits are exhausted, not just the few unique-tag bits.</p>\n<p>So with 32-bit handles, you can always create 4 billion items, with at most\n2^(32 - num_counter_bits) alive at the same time. This also means the number of\nbits for the unique-tag can be reduced without compromising ‘handle safety’.</p>\n<p>It may also be possible to re-activate disabled slots once it can be\nguaranteed that no more handles for that slot are out in the wild\n(maybe at special places in the code like entering or exiting a level).</p>","headings":[{"level":1,"text":"Handles are the better pointers","id":"handles-are-the-better-pointers"},{"level":2,"text":"Move memory management into central systems","id":"move-memory-management-into-central-systems"},{"level":2,"text":"Group items of the same type into arrays","id":"group-items-of-the-same-type-into-arrays"},{"level":2,"text":"Public index-handles instead of pointers","id":"public-index-handles-instead-of-pointers"},{"level":2,"text":"Memory safety considerations","id":"memory-safety-considerations"},{"level":2,"text":"Other useful properties of handles","id":"other-useful-properties-of-handles"},{"level":2,"text":"Some real-world examples","id":"some-real-world-examples"},{"level":2,"text":"Update 28-Nov-2018","id":"update-28-nov-2018"}]}}