8 ms·
Ointers: A library for representing pointers where bits have been stolen (2021)
- couchand 3y agoAm I misreading the bitmask code? It looks like (in addition to a few other ideas) it's using the old "stick a few extra bits in an aligned pointer", but it seems to be only manipulating high bits, whereas aligned pointer zeroes are low-order bits. I'd suggest a heavier investment in testing infrastructure.
- pixelesque 3y agoIt looks like it can use both traditional "tagged pointer" alignment bits AND virtual address bits...
- couchand 3y agoI see that in the readme but I don't see where that's handled in the bitmasking. It appears to be universally masking high-order bits here: https://github.com/irrustible/ointers/blob/1961f75bbb9818d72f59a3601997bf8a34952005/src/lib.rs#L460-L464 https://github.com/irrustible/ointers/blob/1961f75bbb9818d72...
- formerly_proven 3y agoRead the function above the function you linked to.
- couchand 3y agoOh that's frightening they shift the entire pointer by the alignment
- db48x 3y agoWhy? Alignment causes some low–order bits to be zero. Shifting the pointer to the right drops those zeros on the floor, leaving high–order bits zero (or sign extended or whatever). Then you can put your tag up there instead. Shifting the value left by the same amount drops the tag and recovers the same pointer for use.
- vlovich123 3y agoAny idea why it's preferred to do the alignment route instead of storing the bits in the upper part of the pointer & masking?
- db48x 3y agoPersonal preference, architectural differences, phase of the moon, etc, etc.
- couchand 3y agoMy guideline with pointer tricks is: if you're not just masking bits it's too complicated for real use.
- Sharlin 3y agoThe stored representation is packed such that all the stealable bits are contiguous. To get the original pointer value it’s unpacked first.
- masklinn 3y ago64 bit architectures don't actually have 64 bit address spaces, both AMD64 and ARM64 have 48 bit address spaces by default (some CPUs have extensions you can enable to request larger address spaces e.g. LVA on ARM64 and 5LP / LA57 on AMD64 but that's opt-in on a per-process basis). So while you have 3 bits available at the bottom of the pointer, there are 16 at the top. That's a lot more payload you can smuggle. There are even CPU extensions which tell the processor to ignore some of that (Linear Address Masking for Intel, Upper Address Ignore for AMD, and Top Byte Ignore for ARM).
- vlovich123 3y agoSmall correction. That's true for 4-level paging where virtual memory is capped at 256 TiB (LAM48). There's a 5-level extension that reduces the wasted space to 7 bits (LAM57) to allow for 128 PiB of virtual space. I have no idea what the purpose of the extension is that when I don't believe you can get that much secondary storage attached to a CPU unless you go to tape which is pointless for virtual mapping.
- masklinn 3y ago... I literally mentioned five-level paging in my comment. But it's an opt-in extension, you need the kernel to support it, and then you need to ask the kernel to enable it on your behalf. So it's not much of an issue, you just have to not to use this sort of extensions (it's not the only one, ARM64 also has a similar one though it only goes up to 52 bit address spaces) with 16~19 bits of tagging.
- LegionMammal978 3y agoYou do need to opt-in when compiling the kernel, but on Linux it doesn't take anything particularly special on the program's side to enable it. The rule is that non-fixed mmap() will only ever yield 48-bit addresses, until the program specifies a 57-bit address as a hint, after which it can yield 57-bit addresses at will. (This rule has lots of curious consequences for the location of the vDSO, when 5-level paging is enabled and an ELF program uses big addresses for its segments.)
- zgs 3y agoEvery time I've seen similar done in the past, it has come back to hurt the instigator.
- pixelesque 3y agoI've used tagged pointers with no issues at all over the years to "smuggle" / store values in...
- speed_spread 3y agoIf you build your whole app with it, yeah. If you use it tactically for a certain data type it can be very nice. Just don't try to dissimulate it's specialness.
- db48x 3y agoEvery lisp system that ever existed uses this technique, and it never hurt them any. Emacs or SBCL or Open Genera; they all work perfectly well.
- _flux 3y agoOCaml uses the lowest bit, which is nice because (aligned) pointers work as-is.
- lmm 3y ago> Every lisp system that ever existed uses this technique, and it never hurt them any. Wasn't it part of the reason they ended up with poor "mechanical sympathy" on regular PCs, and got a bad performance reputation as a result?
- db48x 3y agoNo. Their reputation for poor performance mostly arises because the default data structure is a singly–linked list. Although the language makes these lists extremely convenient for the programmer to use, linked lists invariably result in terrible cache locality. High–performance systems that are written in lisp (and they do exist), achieve that performance by avoiding lists and using vectors and arenas instead. Of course, it must be said that this performance penalty rarely matters in practice. For most programs, the limiting factor is not performance but the cost of implementation and maintenance. Lisp has has many powerful and convenient features that make implementation faster and surer than in any other language, and which usually greatly lower the cost of maintenance as well. Thus by writing a new program in Lisp you can get it off the ground and earning you money faster than you could in almost any other language. You can also add features more cheaply as time goes on, allowing you to keep up with your competitors. It is only when your system is nearing completion, and all necessary features have been invented and implemented, that you should think about rewriting select parts of that system in a systems language where more efficiency is possible. Not only will you only understand the system after it is written, but you can measure the actual performance of the system to figure out which parts you need to rewrite, and which parts have acceptable performance already and thus do not need to be rewritten.
- gizmo 3y agoStealing bits from pointers makes sense sometimes, but in most cases an easier and less error-prone way to increase memory efficiency is to just use indices or relative pointers. Instead of shaving individual bits of a pointer take advantage of the fact that most pointers in a program are almost exactly alike. Instead of storing a 64 bit prev and next pointer for an item in a linked list just store e.g. two 16 bit offsets. Then the next_ptr = (this_ptr & base_mask) + offset * alignment. Most of the time wasting memory by storing full 64bit pointers is no big deal. But when it is, you can go a lot further than just shaving off a few bits. If you want to be extra clever you can encode values in the base address of your pointers by taking advantage of how virtual memory is allocated. Every process has its own virtual memory pages and you can request memory pages at specific address ranges. For instance if you align all your memory at a 32gb boundary then you can use 32bit pointers + a base pointer without even having to mask. You can also use virtual memory allocation tricks to convey information about alignment, typing, whether a pointer is allowed to be shared between threads and so on. And again, without having to butcher the pointer itself.
- jsheard 3y agoConsidering how common it is to use indices in lieu of pointers in Rust, it would be nice if it had native NonMax integer types similar to the NonZero types it already has. NonZero gives you the niche-filling optimization (e.g. Option<NonZero> and NonZero are the same size) but with indices you want zero to be a valid value, so it would be natural to use the maximum as the illegal value instead. You can kind of do it by offsetting the index by 1 or inverting the bits then putting it in a NonZero but that's a small extra runtime cost on every use.
- joseluis 3y agoYou can do a handy struct wrapper over a private Nonzero that xors the given value with the prohibited value (max in this case) at the new constructor. And like so for the get method. Xoring is very cheap. That's my favorite way of storing indices/links for nodes, since you can wrap them in Option for free.
- 3y ago
- pavlov 3y agoTechnically it’s an ointer on PowerPC and SPARC, but a pointe everywhere else.
- sojuz151 3y agoThis look like something that debuggers would hate, because following pointers would be broken
- jxf 3y agoI was just thinking this. You'd either need to special-case your debuggers or be able to use something that provided bespoke hooks for pointer-following.
- gpderetta 3y agoWrap it in a class and teach the debugger to interpret it. It might be possible with gdb and python pretty-printers for example.
- zozbot234 3y agoAre there ways on Linux to make sure that all user-visible pointers in a process are allocated within some subset of the overall address space? For instance, imagine writing a 64-bit program such that all userspace pointers are allocated within the first 32 bits. This would allow for representing them in memory using four bytes, as is commonly done on 32-bit architectures--without adding more extensive or ad-hoc changes such as a new "x32" binary format. Except that you could also limit to 24-bit (giving 16M of address space), 16-bit (for a "tiny" code model) or anything else. Of course, this would require some amount of support in the linker/loader, userspace libraries and the kernel itself. But the effort might be worthwhile if it can allow for replacing more ad-hoc approaches.
- fathyb 3y agoAn allocator is free to only `mmap` addresses that are within a range. I think jemalloc could allow you to do that using custom arenas.
- ksherlock 3y agoLinux mmap (since 2.6) has a MAP_32BIT flag, but only for x86-64: Put the mapping into the first 2 Gigabytes of the process address space. This flag is supported only on x86-64, for 64-bit programs. It was added to allow thread stacks to be allocated somewhere in the first 2 GB of memory, so as to improve context-switch performance on some early 64-bit processors. Modern x86-64 processors no longer have this performance problem, so use of this flag is not required on those systems. The MAP_32BIT flag is ignored when MAP_FIXED is set.
- o11c 3y agoASAN relies on kernel internal details, but this has broken a few times. Realistically you should just mmap a huge aligned chunk in the first place, then allocate inside that.
- asb 3y agoI somehow hadn't come across this library, but have a whole blog post on the various ways people store data in pointers (and when+why it's safe) https://muxup.com/2023q4/storing-data-in-pointers https://muxup.com/2023q4/storing-data-in-pointers
- makz 3y agoAwesome, been looking for this information for ages already.
- queuebert 3y agoIf the ointer points to a very large block of memory, is it an oinker?
- willcipriano 3y agoI never had the problem of too many pointers, but if I did I'd try the "arena"[0] approach. Preallocate a huge area of memory and use smaller indexes relative to the start instead. Provided a pointer is bigger than a int. You might be able to use this in that approach and keep partial pointers instead. [0]https://www.rfleury.com/p/untangling-lifetimes-the-arena-allocator https://www.rfleury.com/p/untangling-lifetimes-the-arena-all...
- gumby 3y ago> What do you call a pointer with the high bits stolen? An ointer! What is the name a pointer with the low bits stolen? Machines with strict word addressing will ignore the bottom two bits so you can safely store what you want there. Not sure I've used, much less programmed a machine with that strict constraint in a while though. These days CPUs are all designed to implement the C abstract machine. At least the GPU folks are not subject to this constraint.
- gwbas1c 3y agoCould something like this be used to lower memory footprint?
- menaerus 3y agoBesides that it makes some lock-free algorithms even feasible and some easier to implement, yes, it also can be used to downsize the memory pressure at the cost of extra CPU cycles if you know that the metadata you want to track fits in those 16+ bits.
- malkia 3y agoI've posted about MGS PS1 port we did to PC and how some pointers to the C4 bomb planted posted meant it was on the wall or on the ground - here -> https://news.ycombinator.com/item?id=9739731 https://news.ycombinator.com/item?id=9739731 to quote me: - The game used a tricky pointer hack, basically on the PSX accessing a pointer with the highest-24-bit set means read it from the CPU cache, otherwise not (or maybe the other way around). This was used for example to indicate whether the C4 bomb was planted on the ground, or on the wall instead of keeping a booblean/bit flag for it. Possibly was used for some more things. Since it was 24-bit, that meant 16mb.