Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Storing data in pointers

muxup.com

Post reply on HN
Print view View original

61–70 of 71 posts

Re: Storing data in pointers

#61

Post by spacechild1 »

teh_matt wrote: post #4
spacechild1 wrote: post #3

Earlier quoted context omitted.

It is also very useful for some lockfree algorithms, e.g. to fit a pointer and a sequence number within a 64-bit value.

You should be very careful when doing that. It may be rare in practice, but it's surprisingly easy to trigger ABA issues with only a 16-bit sequence number.

I don't really believe that it is easy to trigger. The thread would have to be preempted at a very specific point for a very specific duration, the other thread(s) would need to perform exactly 2^16 operations within that time window and the final operation would need to trigger the ABA problem. Possible, but extremely unlikely. (In some applications even impossible.) Do you happen to have some real world examples?

But yes, it is definitely something to be aware of!

BTW, if the pointers are always aligned, the sequence number may have a few bits more.

Re: Storing data in pointers

#62

Post by dmt314159 »

This will be a problem when trying this on Capability Hardware Enhanced RISC Instructions (CHERI) https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/ systems. Currently the only CPU with this implemented is Arm's Morello prototype.

Pointers are replaced by 128-bit capabilities containing what operations are valid, a 64-bit base address and a size. These capabilities are unforgeable, so trying to play with "unused" parts of 64-bit pointers simply won't work.

FreeBSD & Gnome are running on hardware after minor source-code changes, along with a significant proportion of FreeBSD ports collection.

As well as ARM, Microsoft is interested: https://www.microsoft.com/en-us/research/project/portmeirion...

Re: Storing data in pointers

#63

Post by yencabulator »

marcus_holmes wrote: post #13

I looked at the Go implementation of this in "tagged pointers" [0] The amount of data that can be used for the tag is architecture-dependant, and the routine discards any tag bits that don't fit into the tagged pointer without telling the caller. To me, this seems ridiculous - why not just use a struct with a tag and a pointer, and not run the risk of your tag being destroyed without you knowing because the architect…

It's up to the low-level code to stay within taggedPointerBits, and the value is arch-dependent.

For netpoll, it looks to be just a cyclic epoch counter, so the size doesn't really matter: https://github.com/golang/go/blob/4956c3437bd2f4448bcec51321...

For use in malloc, it's assumed to be >=10 and verified at init: https://github.com/golang/go/blob/4956c3437bd2f4448bcec51321...

Re: Storing data in pointers

#64

Post by marcus_holmes »

intelVISA wrote: post #25
marcus_holmes wrote: post #13

I looked at the Go implementation of this in "tagged pointers" [0] The amount of data that can be used for the tag is architecture-dependant, and the routine discards any tag bits that don't fit into the tagged pointer without telling the caller. To me, this seems ridiculous - why not just use a struct with a tag and a pointer, and not run the risk of your tag being destroyed without you knowing because the architect…

It is not a Go thing, tagged pointers have been around forever!!

I didn't say it was. I just followed one of the links in the article because I grok Go and it seemed counter-intuitive to how Go normally does things. But the other answers seem to make sense, so I guess this is a thing I accept now.

Re: Storing data in pointers

#65

Post by ithkuil »

vidarh wrote: post #24
jandrese wrote: post #5

Very old Macs used this trick to squeeze their ROM routines down a bit, operating with 24 bit addressing and using the top bits for flags and whatnot. Of course they ran into trouble when machines with 16MB of memory started appearing. If you do this you might be making more work for yourself in the future when you buy a new machine with 256EB of main memory.

I'm guessing the problem occurred specifically with CPUs newer than the 68000 irrespective of amount of RAM? (Microsoft's) Amiga Basic also did this and stopped working on newer CPUs, as the 68000 only has 24 address lines and ignores the top 8 bits of a 32 bit address, but 68020 and up uses all 32 (I don't remember about the 68010, but that was pin compatible with the 68000 so I'm guessing not)

The 68010 was indeed pin compatible with the 6800 and had only 24 address bits.

But the 68012 (which was otherwise software compatible with the 68010) extended the address bus (and had more pins) and was the first m68k CPU to exhibit this compat issue.

The 68020 was more popular but came a couple of years later

Re: Storing data in pointers

#66

Post by vidarh »

ithkuil wrote: post #65
vidarh wrote: post #24

Earlier quoted context omitted.

I'm guessing the problem occurred specifically with CPUs newer than the 68000 irrespective of amount of RAM? (Microsoft's) Amiga Basic also did this and stopped working on newer CPUs, as the 68000 only has 24 address lines and ignores the top 8 bits of a 32 bit address, but 68020 and up uses all 32 (I don't remember about the 68010, but that was pin compatible with the 68000 so I'm guessing not)

The 68010 was indeed pin compatible with the 6800 and had only 24 address bits. But the 68012 (which was otherwise software compatible with the 68010) extended the address bus (and had more pins) and was the first m68k CPU to exhibit this compat issue. The 68020 was more popular but came a couple of years later

That's interesting. I'm not sure I was ever aware of the 68012.

Re: Storing data in pointers

#67

Post by ithkuil »

vidarh wrote: post #66
ithkuil wrote: post #65

Earlier quoted context omitted.

The 68010 was indeed pin compatible with the 6800 and had only 24 address bits. But the 68012 (which was otherwise software compatible with the 68010) extended the address bus (and had more pins) and was the first m68k CPU to exhibit this compat issue. The 68020 was more popular but came a couple of years later

That's interesting. I'm not sure I was ever aware of the 68012.

Possibly only used by Alliant

Re: Storing data in pointers

#68

Post by rr808 »

userbinator wrote: post #19
rr808 wrote: post #9

My favorite hack back in MFC days was a combo box which I stored the pointer address in the text (to the right after a lot of spaces so was hidden). When a user chooses an item, parse the pointer and de-reference it back to an object.

I guess you didn't come across CB_SETITEMDATA / CB_GETITEMDATA ?

Damn that brings back memories. There was a reason I didn't choose for that dialog, it was such a long time ago.

Re: Storing data in pointers

#69

Post by masklinn »

Dylan16807 wrote: post #54
masklinn wrote: post #53

Earlier quoted context omitted.

> The allocator gets address space. The allocator gets address space from the OS . > The OS doesn't just shove things into your process in general. It can't return a 52 bit pointer out of nowhere. My first draft mentioned OS explicitly but it's not really the OS that's making the decisions. Of course it’s the OS making the decision. You ask the OS for memory and it returns whatever it wants. The allocators acts as br…

The allocator can choose which part of the address space to fill. It does not have to deal with "whatever the OS wants". > It absolutely is necessary, since the entire subject is to not break applications requiring a smaller address space for their tagging scheme to work even as the system and other applications migrate to larger ones. Even if you have a 1:1 memory mapping, you can leave the applications that want sm…

> The allocator can choose which part of the address space to fill.

No it can not. The allocator can request which part of the address space to fill, and the OS is completely free to ignore that request.

> It does not have to deal with "whatever the OS wants".

It absolutely does, the OS is ultimately who controls both the physical and virtual address spaces.

> Even if you have a 1:1 memory mapping, you can leave the applications that want small addresses at the start of memory.

Up until it’s all taken and then you can’t do that anymore.

Re: Storing data in pointers

#70

Post by Dylan16807 »

masklinn wrote: post #69
Dylan16807 wrote: post #54

Earlier quoted context omitted.

The allocator can choose which part of the address space to fill. It does not have to deal with "whatever the OS wants". > It absolutely is necessary, since the entire subject is to not break applications requiring a smaller address space for their tagging scheme to work even as the system and other applications migrate to larger ones. Even if you have a 1:1 memory mapping, you can leave the applications that want sm…

> The allocator can choose which part of the address space to fill. No it can not. The allocator can request which part of the address space to fill, and the OS is completely free to ignore that request. > It does not have to deal with "whatever the OS wants". It absolutely does, the OS is ultimately who controls both the physical and virtual address spaces. > Even if you have a 1:1 memory mapping, you can leave the…

> the OS is completely free to ignore that request

I'm assuming an OS that isn't refusing to do things for no reason.

Aren't you?

If we're accounting for capricious refusal of program allocation requests, then 64-bit clean programs can't safely run either.

> Up until it’s all taken

Which is no worse than it was before you upgraded your RAM.

Not that anyone is running big programs on systems without MMUs.

Post reply on HN