Hi everyone,
I'm reading Andrei's book (amazing!) and studying the sources of Loki.
Unfortunately, I don't understand how the deallocation of small objects works.
That is, how to map a "naked" pointer to its corresponding chunk.
The problem I'm seeing is that, according to my reading of 5.9 (relational operators) of the standard, the condition
( pData_ <= pc ) && ( pc < pData_ + chunkLength )
could evaluate to true even if pc points *outside* that block because the value of such a condition would be unspecified in the very case we are trying to check.
The standard says
--SNIP--
If two pointers p and q of the same type point to different objects
that are not members of the same object or elements of the same
array or to different functions, or if only one of them is null, the
results of p<q, p>q, p<=q, and p>=q are unspecified.
--SNIP--
Suppose you have two chunks, C1 and C2, and a pointer pc returned by an allocation performed by C2 (that is, pc points inside C2->pData).
If we check whether C1 owns pc we could (wrongly) deduce that it does because the value of
( pData_ <= pc ) && ( pc < pData_ + chunkLength )
both operands would be unspecifed, so the whole expression could be evaluated to true.
Am I missing something?
Cheers,
Giovanni
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Before answering your question, I would like to inform you that the source code does not match the book anymore. I rewrote most of this part of Loki to improve runtime performance. I kept much of the low-level code in the allocator because I liked how Andrei designed it, but the higher level stuff looks and acts differently.
I initially reacted to that snippet from the C++ Standard with "Huh? That does not make sense." I have seen many such pointer comparisons without any ill effects. Also, the allocator passes all the tests on the Linux and Windows operating systems I used.
Since paragraph 5.9/2 of the standard does match what you wrote, we can wonder what the original authors had in mind when writing this. Perhaps they simply meant to imply that we should not assume a flat memory model (i.e. - with pointers as "integers").
Anyhow, if you discover that comparison leads to incorrect behavior when Loki is made with any compiler on any operating system, please let me know! Loki and other allocators need that comparison to work all the time.
Thanks,
Rich
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Hi Rich,
thank you very much for the clarifications.
Indeed, I've noticed that the sources don't match the ones described in the book, but I still find the book very useful (I'm pretty new to these "extreme" ;-) uses of templates). I've also noticed that the current library is bigger, I'll study the new components too :-)
Regarding the standard, I agree with you. They probably wanted to allow non-flat memory models. For instance, if I remember correctly, in the old 16 bit era of x86 the pointers consisted of a segment and an offset, and the actual memory address was equal to 16*segment+offset (or something similar). You couldn't compare those pointers, treating them as big integers, without a "normalization" step or the results were ehm... "funny".
I find the comparison used by Loki quite intuitive and sensible, and I'm sure it works in modern architectures (at least the ones I know), but I've found it strange that Andrei wrote something relying on an unspecified behaviour without mentioning it.
Kind regards,
Giovanni
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Hi everyone,
I'm reading Andrei's book (amazing!) and studying the sources of Loki.
Unfortunately, I don't understand how the deallocation of small objects works.
That is, how to map a "naked" pointer to its corresponding chunk.
The problem I'm seeing is that, according to my reading of 5.9 (relational operators) of the standard, the condition
( pData_ <= pc ) && ( pc < pData_ + chunkLength )
could evaluate to true even if pc points *outside* that block because the value of such a condition would be unspecified in the very case we are trying to check.
The standard says
--SNIP--
If two pointers p and q of the same type point to different objects
that are not members of the same object or elements of the same
array or to different functions, or if only one of them is null, the
results of p<q, p>q, p<=q, and p>=q are unspecified.
--SNIP--
Suppose you have two chunks, C1 and C2, and a pointer pc returned by an allocation performed by C2 (that is, pc points inside C2->pData).
If we check whether C1 owns pc we could (wrongly) deduce that it does because the value of
( pData_ <= pc ) && ( pc < pData_ + chunkLength )
both operands would be unspecifed, so the whole expression could be evaluated to true.
Am I missing something?
Cheers,
Giovanni
Hi Giovanni,
Before answering your question, I would like to inform you that the source code does not match the book anymore. I rewrote most of this part of Loki to improve runtime performance. I kept much of the low-level code in the allocator because I liked how Andrei designed it, but the higher level stuff looks and acts differently.
I initially reacted to that snippet from the C++ Standard with "Huh? That does not make sense." I have seen many such pointer comparisons without any ill effects. Also, the allocator passes all the tests on the Linux and Windows operating systems I used.
Since paragraph 5.9/2 of the standard does match what you wrote, we can wonder what the original authors had in mind when writing this. Perhaps they simply meant to imply that we should not assume a flat memory model (i.e. - with pointers as "integers").
Anyhow, if you discover that comparison leads to incorrect behavior when Loki is made with any compiler on any operating system, please let me know! Loki and other allocators need that comparison to work all the time.
Thanks,
Rich
Hi Rich,
thank you very much for the clarifications.
Indeed, I've noticed that the sources don't match the ones described in the book, but I still find the book very useful (I'm pretty new to these "extreme" ;-) uses of templates). I've also noticed that the current library is bigger, I'll study the new components too :-)
Regarding the standard, I agree with you. They probably wanted to allow non-flat memory models. For instance, if I remember correctly, in the old 16 bit era of x86 the pointers consisted of a segment and an offset, and the actual memory address was equal to 16*segment+offset (or something similar). You couldn't compare those pointers, treating them as big integers, without a "normalization" step or the results were ehm... "funny".
I find the comparison used by Loki quite intuitive and sensible, and I'm sure it works in modern architectures (at least the ones I know), but I've found it strange that Andrei wrote something relying on an unspecified behaviour without mentioning it.
Kind regards,
Giovanni