On 4/11/2011 1:54 PM, Nevin Liber wrote:

On 11 April 2011 14:47, Phil Bouchard<philippe@fornux.com> wrote:

...

I see the Boost.Pool is not making its way up to the C++ standards yet an it is very unfortunate given its great use. Boost.Pool provides an is_from() member function that does a simple range check and returns whether a pointer is part of the pool or not. This is a very useful function which I think should be part of the standards because it could be used for the global pool as well; i.e. the one used by operator ::new and ::delete. The benefits outweigh the costs.

What are the costs?

The cost of having to pollute the global namespace.

As far as I know, there is no requirement that the heap be contiguous.

I meant range checks of the heap memory pages...

Plus, the intent is that implementations can use C's malloc calls, and the malloc interface doesn't expose this.

This is actually surprising.

If you seriously want this feature, contact your friendly neighborhood C committee member... :-)

I will, thanks. -Phil

On 4/11/2011 6:02 PM, Dave Abrahams wrote:

Whatever the costs, you have a point because this is something that can only be implemented portably by the standard. I'm certain that Boost.Pool invokes undefined behavior whenever it returns false from is_from().

Indeed 'false' basically means your not sure if the pointer will eventually be part of the pool or not but 'true' is authoritative in its quest to locate a current object. -Phil

On 4/11/2011 11:19 PM, Nevin Liber wrote:

On 11 April 2011 22:40, Phil Bouchard<philippe@fornux.com> wrote:

...

On 4/11/2011 6:02 PM, Dave Abrahams wrote:

...

Whatever the costs, you have a point because this is something that can only be implemented portably by the standard. I'm certain that Boost.Pool invokes undefined behavior whenever it returns false from is_from().

Indeed 'false' basically means your not sure if the pointer will eventually be part of the pool

But it may be undefined behavior to pass that pointer to is_from.

That's right but I am not sure about the complexity in making its behavior non-undefined even if the complexity is not constant. Because otherwise is_from() would be quite useless if a non-true value crashes the application.

...

or not but 'true' is authoritative in its quest to locate a current object.

But it doesn't tell whether the object was directly allocated in that pool or if it was indirectly allocated by being an aggregate in another data structure.

Well it tells you whether an object or one of its aggregate is within any of the memory pages reserved by the pool.

What exactly is the benefit of this?

To make it generic in order to standardize memory management eventually because most of them make use of a stack / heap differentiation function. A ::pool.is_from() call could be a solution. I fail to see any hope in standardizing memory management without this. Thanks, -Phil

On Apr 12, 2011, at 3:54 AM, Phil Bouchard <philippe@fornux.com> wrote: On 4/11/2011 11:19 PM, Nevin Liber wrote: On 11 April 2011 22:40, Phil Bouchard< <philippe@fornux.com> philippe@fornux.com> wrote: On 4/11/2011 6:02 PM, Dave Abrahams wrote: Whatever the costs, you have a point because this is something that can only be implemented portably by the standard. I'm certain that Boost.Pool invokes undefined behavior whenever it returns false from is_from(). Indeed 'false' basically means your not sure if the pointer will eventually be part of the pool But it may be undefined behavior to pass that pointer to is_from. That's right but I am not sure about the complexity in making its behavior non-undefined even if the complexity is not constant. Because otherwise is_from() would be quite useless I think you are severely missing the point: it is not implementable, no matter the cost in complexity, without causing undefined behavior. You're just not allowed to compare arbitrary pointers with <, and the total ordering produce by std::less isn't guaranteed to be meaningful.

On Tue, Apr 12, 2011 at 11:15 AM, Steven Watanabe <watanabesj@gmail.com> wrote:

AMDG

On 04/12/2011 08:04 AM, Dave Abrahams wrote:

...

On Apr 12, 2011, at 3:54 AM, Phil Bouchard<philippe@fornux.com>  wrote:

...

On 4/11/2011 11:19 PM, Nevin Liber wrote:

...

But it may be undefined behavior to pass that pointer to is_from.

That's right but I am not sure about the complexity in making its behavior non-undefined even if the complexity is not constant.  Because otherwise is_from() would be quite useless

I think you are severely missing the point: it is not implementable, no matter the cost in complexity, without causing undefined behavior. You're just not allowed to compare arbitrary pointers with<, and the total ordering produce by std::less isn't guaranteed to be meaningful.

Sure it's implementable.  You just have to compare it for /equality/ with every address inside the pool.  You should be able to enumerate them.

Hahaha, you're quite right! It's implementable, but could be really expensive. Thanks for the correction. I wonder if compilers will optimize away the loop? -- Dave Abrahams BoostPro Computing http://www.boostpro.com

On 12 April 2011 11:53, Phil Bouchard <philippe@fornux.com> wrote:

On 4/12/2011 8:04 AM, Dave Abrahams wrote:

...

I think you are severely missing the point: it is not implementable, no matter the cost in complexity, without causing undefined behavior. You're just not allowed to compare arbitrary pointers with<, and the total ordering produce by std::less isn't guaranteed to be meaningful.

Thanks for the clarifications but if the stack and data segments were part of a pool then 'false' returned by is_from() would then be a valid according to the definition of is_from().

Only if it is implemented the way Steven described it. You cannot legally compare pointers using relationship operators (<, <=, >, >=) unless at least one is NULL, they are both pointing within the same object, or both pointing within the same array (or just past the end of the array). All other comparisons are undefined behavior. See 6.5.8 of the C99 standard for a much more precise definition. -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404

On 12 April 2011 12:55, Dave Abrahams <dave@boostpro.com> wrote:

At Tue, 12 Apr 2011 12:15:56 -0500, Nevin Liber wrote:

...

Only if it is implemented the way Steven described it. You cannot legally compare pointers using relationship operators (<, <=, >, >=) unless at least one is NULL,

really, in C++ you can do it if one is NULL? What result do you get?

Oops, you can't. The null pointer constant only matters when using equality operators. -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404

On 12 April 2011 16:46, Phil Bouchard <philippe@fornux.com> wrote:

On 4/12/2011 10:15 AM, Nevin Liber wrote:

...

Only if it is implemented the way Steven described it. You cannot legally compare pointers using relationship operators (<,<=,>,>=) unless at least one is NULL, they are both pointing within the same object, or both pointing within the same array (or just past the end of the array). All other comparisons are undefined behavior. See 6.5.8 of the C99 standard for a much more precise definition.

I understand but a memory page is in general aligned and therefore the pointer difference (ptrdiff) of the beginning of the page with the location of the object can be valid. In other words the memory page can be an array of type T.

I'm not saying that it won't accidentally work, but once you have undefined behavior, the compiler is free to do anything it wants. And once you are talking about pages of memory, you are (IMHO) outside of the realm of what can be standardized within the language, since you are now OS and/or hardware specific. I'd still like to see a small example showing the usefulness of such a feature. -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404

On 12 April 2011 17:01, Nevin Liber <nevin@eviloverlord.com> wrote:

On 12 April 2011 16:46, Phil Bouchard <philippe@fornux.com> wrote:

...

On 4/12/2011 10:15 AM, Nevin Liber wrote:

...

Only if it is implemented the way Steven described it. You cannot legally compare pointers using relationship operators (<,<=,>,>=) unless at least one is NULL, they are both pointing within the same object, or both pointing within the same array (or just past the end of the array). All other comparisons are undefined behavior. See 6.5.8 of the C99 standard for a much more precise definition.

I understand but a memory page is in general aligned and therefore the pointer difference (ptrdiff) of the beginning of the page with the location of the object can be valid. In other words the memory page can be an array of type T.

I'm not saying that it won't accidentally work, but once you have undefined behavior, the compiler is free to do anything it wants.

To illustrate this, take the following code: struct Silly { bool is_from(const char* p) { return buffer <= p && p < buffer + sizeof(buffer); } char buffer[1024]; }; I believe that a compiler could legally optimize the body of Silly::is_from to be: { return true; } because in the defined behavior case it returns true, and the compiler can do whatever it wants in the undefined behavior case. As Dave pointed out, the Boost-related issue is that Bool.Pool has a function relying on underfined behavior... -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404

On 4/12/2011 4:06 PM, Phil Bouchard wrote:

Is that so? I guess it'll be different if you have:

struct Silly { bool is_from_heap(const char* p) { return heap<= p&& p< heap + sizeof(heap); }

char data[1024]; char heap[1024]; char stack[1024]; };

... and "p" is guaranteed to be part of either the data, heap or stack buffer. -Phil

On 4/12/2011 3:41 PM, Nevin Liber wrote:

To illustrate this, take the following code:

struct Silly { bool is_from(const char* p) { return buffer<= p&& p< buffer + sizeof(buffer); }

char buffer[1024]; };

I believe that a compiler could legally optimize the body of Silly::is_from to be: { return true; }

because in the defined behavior case it returns true, and the compiler can do whatever it wants in the undefined behavior case.

Once again if is_from() was implemented the following way: bool is_from(const char* p) { return p - buffer > 0 && p - buffer < sizeof(buffer); } Then the undefined behaviors would seem to go away. -Phil

On 4/12/2011 6:52 PM, Nevin Liber wrote:

On 12 April 2011 20:17, Phil Bouchard<philippe@fornux.com> wrote:

...

Once again if is_from() was implemented the following way:

bool is_from(const char* p) { return p - buffer> 0&& p - buffer< sizeof(buffer); }

Then the undefined behaviors would seem to go away.

What makes you believe that? Read the section on pointer arithmetic in the C99 standard.

(Unless this comes back to being Boost related, we really ought to move this discussion out of here.)

5.7.6 covers this issue already hahaha. It looks like the data, heap and stack pools in ::process will simply need to be contiguous. -Phil

On 4/12/2011 9:18 PM, Phil Bouchard wrote:

It looks like the data, heap and stack pools in ::process will simply need to be contiguous.

Any objections? -Phil

On 20:59, Phil Bouchard wrote:

Once again if is_from() was implemented the following way: bool is_from(const char* p) { return p - buffer > 0 && p - buffer < sizeof(buffer); }

Then the undefined behaviors would seem to go away.

Or if std::less would be used instead of operator<. struct Silly { bool is_from(const char* p) { return !std::less<const char*>()(p, buffer) && std::less<const char*>()(p, buffer + sizeof(buffer)); } char buffer[1024]; }; Regards, Anders Dalvander -- WWFSMD?

On 20:59, Nevin Liber wrote:

While the undefined behavior goes away, all that std::less guarantees is a total ordering for pointers. It doesn't specify what that ordering actually is.

True, the actual order isn't defined. But I don't see the issue. Externally a contiguous memory block would be seen as a singleton and comparing it using std::less to any other contiguous memory block would result in either true or false. Internally a contiguous memory block has defined order. Regards, Anders Dalvander -- WWFSMD?

On 04/13/2011 10:40 AM, Dave Abrahams wrote:

On Wed, Apr 13, 2011 at 1:32 PM, Anders Dalvander<boost@dalvander.com> wrote:

...

On 20:59, Nevin Liber wrote:

...

While the undefined behavior goes away, all that std::less guarantees is a total ordering for pointers. It doesn't specify what that ordering actually is.

True, the actual order isn't defined. But I don't see the issue.

Externally a contiguous memory block would be seen as a singleton and comparing it using std::less to any other contiguous memory block would result in either true or false.

The issue is that if you test an address for being within a given memory block, you can get false positives.

Oh, and to make things worse, IIRC there's nothing that says a< b == std::less<...>()(a,b) even within a given block, e.g. std::less<>()(a,b) could be implemented as a> b! So you can get false negatives, too.

Perhaps the real question is whether there exists a C++ compiler that we care about this working on that doesn't behave as we'd like. Not everything left undefined by the standard was necessarily a good decision.

On 2011-04-13 19:40, Dave Abrahams wrote:

On Wed, Apr 13, 2011 at 1:32 PM, Anders Dalvander<boost@dalvander.com> wrote:

...

Externally a contiguous memory block would be seen as a singleton and comparing it using std::less to any other contiguous memory block would result in either true or false.

The issue is that if you test an address for being within a given memory block, you can get false positives.

But that's just the deal, we don't have to test, std::less does it for us.

Oh, and to make things worse, IIRC there's nothing that says a< b == std::less<...>()(a,b) even within a given block, e.g. std::less<>()(a,b) could be implemented as a> b! So you can get false negatives, too.

Don't think so, 20.3.3/5 states: template <class T> struct less : binary_function<T,T,bool> { bool operator()(const T& x, const T& y) const; }; operator() returns x < y.

...

WWFSMD?

Advance the tape!

Probably the best, although slow, thing to do. Regards, Anders Dalvander

On 2011-04-13 20:10, Nevin Liber wrote:

On 13 April 2011 13:01, Anders Dalvander <boost@dalvander.com <mailto:boost@dalvander.com>> wrote:

Don't think so, 20.3.3/5 states:

template <class T> struct less : binary_function<T,T,bool> { bool operator()(const T& x, const T& y) const; };

operator() returns x < y.

Which doesn't apply to pointers.

You are underquoting and context was lost. I was replying to Dave:

...

Oh, and to make things worse, IIRC there's nothing that says a< b == std::less<...>()(a,b) even within a given block

x < y applies to pointers, if they belong to the same block. 20.3.3/8 extend that promise:

"For templates greater, less, greater_equal, and less_equal, the specializations for any pointer type yield a total order, even if the built-in operators <, >, <=, >= do not."

Regards, Anders Dalvander -- WWFSMD?

On 4/13/2011 12:49 PM, Nevin Liber wrote:

x< y has a specified order for pointers pointing within the same array or object, but is undefined for pointers not pointing in the same array or object.

std::less guarantees a total ordering for all pointers, but does not specify what that ordering is, even for pointers pointing within the same array or object (as the pointer specialization is not required to use x< y to do any comparisons).

To make is_from work, we need a total, *specified* ordering for all pointers. I see no way to combine the above two to get a total specified ordering.

There is s bug in the standards because according to 5.2.10/4 a pointer can be converted to an integral type to later be ordered. i.e.: struct Silly { bool is_from(const char* p) { return !std::less<long>()(reinterpret_cast<long>(p), reinterpret_cast<long>(buffer)) && std::less<long>()(reinterpret_cast<long>(p), reinterpret_cast<long>(buffer + sizeof(buffer))); } char buffer[1024]; }; -Phil

On 4/13/2011 3:26 PM, Dave Abrahams wrote:

At Wed, 13 Apr 2011 14:17:15 -0700, Phil Bouchard wrote:

...

...

To make is_from work, we need a total, *specified* ordering for all pointers. I see no way to combine the above two to get a total specified ordering.

There is s bug in the standards because according to 5.2.10/4 a pointer can be converted to an integral type to later be ordered. i.e.:

struct Silly { bool is_from(const char* p) { return !std::less<long>()(reinterpret_cast<long>(p), reinterpret_cast<long>(buffer))&& std::less<long>()(reinterpret_cast<long>(p), reinterpret_cast<long>(buffer + sizeof(buffer))); }

char buffer[1024]; };

Stop, stop, seriously. That's not a bug, and your code isn't guaranteed to produce any particular result either, portably. reinterpret_cast has unspecified or implementation-defined results (I forget which) in this case.

It's implementation defined.

If you don't believe me, take the question to some "higher authority" on the C++ core standard, such as you might find on comp.std.c++, but please stop wasting time arguing with me about it in this forum.

I did take the issue to comp.std.c++ but it was unclear whether is_from was affected.

I fear my whole point was missed: since there's no way to implement is_from in portable standard-compliant user code, it makes sense that (if it's actually broadly needed) it should go in the standard as you suggested, and as a first step, it should go in Boost.

Thanks, -Phil

AMDG On 04/13/2011 08:32 PM, Phil Bouchard wrote:

On 4/13/2011 3:45 PM, Phil Bouchard wrote:

...

On 4/13/2011 3:26 PM, Dave Abrahams wrote:

...

Stop, stop, seriously. That's not a bug, and your code isn't guaranteed to produce any particular result either, portably. reinterpret_cast has unspecified or implementation-defined results (I forget which) in this case.

It's implementation defined.

Please apologize my tenacity but the C standard defines intptr_t to be the same size as a pointer.

You're missing the point. The only thing the standard guarantees about casting a pointer to intptr_t is that it's reversible.

This is defined in "cstdint" so consequently we could use:

struct Silly { bool is_from(const char* p) { return !std::less<intptr_t>()(reinterpret_cast<intptr_t>(p), reinterpret_cast<intptr_t>(buffer)) && std::less<intptr_t>()(reinterpret_cast<intptr_t>(p), reinterpret_cast<intptr_t>(buffer + sizeof(buffer))); }

char buffer[1024]; };

In Christ, Steven Watanabe

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 AMDG On 04/13/2011 09:27 PM, Phil Bouchard wrote:

On 4/13/2011 8:56 PM, Steven Watanabe wrote:

...

You're missing the point. The only thing the standard guarantees about casting a pointer to intptr_t is that it's reversible.

7.4.1.5 Integer types capable of holding object pointers

It sounds to me I can save the value of cast to an integer and do whatever I want with it such as ordering.

Yes, but... The order you get is entirely implementation defined. In Christ, Steven Watanabe -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJNpvvQAAoJEDTBQuhymLHSKG8IAIhS4KLy2RAzYSgJv2Hfbb16 j+vDae46RWP1iPPaDplADyqRJCOrtLj+QH5bDaYFj4eIAtFCXyDSjZAFpw6LBHVR XK62XEz62X0expf2SSr1IoiyW1aqB69gGV/0wmwtEQ093eklbmO4ksuGt3RzKwha 08pPQwJ02/KF3RpYNcR/T8i96kvJ/f5jxKNRUfr/mUY3ne4EB5rdaFHsMLHcglNz xOSaQ74IIHo0mN71yRH/D6/hFQGYISo6xemHNQNt1etuw6jksqusMMn0RjHHG4Q7 3m7ZPR5FOR5yvbsnoglCUGcxfKXthNoa0KYt2iYCPIyi9h68MroVeSiZ8lBVy5A= =uk5V -----END PGP SIGNATURE-----

On 13 Apr 2011, at 23:26, Dave Abrahams wrote:

At Wed, 13 Apr 2011 14:17:15 -0700, Phil Bouchard wrote:

...

...

To make is_from work, we need a total, *specified* ordering for all pointers. I see no way to combine the above two to get a total specified ordering.

There is s bug in the standards because according to 5.2.10/4 a pointer can be converted to an integral type to later be ordered. i.e.:

struct Silly { bool is_from(const char* p) { return !std::less<long>()(reinterpret_cast<long>(p), reinterpret_cast<long>(buffer)) && std::less<long>()(reinterpret_cast<long>(p), reinterpret_cast<long>(buffer + sizeof(buffer))); }

char buffer[1024]; };

Stop, stop, seriously. That's not a bug, and your code isn't guaranteed to produce any particular result either, portably. reinterpret_cast has unspecified or implementation-defined results (I forget which) in this case.

If you don't believe me, take the question to some "higher authority" on the C++ core standard, such as you might find on comp.std.c++, but please stop wasting time arguing with me about it in this forum.

I fear my whole point was missed: since there's no way to implement is_from in portable standard-compliant user code, it makes sense that (if it's actually broadly needed) it should go in the standard as you suggested, and as a first step, it should go in Boost.

There are other places in Boost which make use of undefined behaviour. Further, lots of bits of boost are compiler-specific, and many compilers guarantee that is_from with < will work fine. In every standard library I have ever seen, std::less for pointers is just defined using <. Further, < works on all pointers, because all C++ compilers I'm aware of allow code which works on raw memory, without malloc/new. Unless anyone produces a compiler which compiles even a tiny part of Boost and miscompiles any of this code, I would just leave it. Chris

On 2011-04-13 20:22, Dave Abrahams wrote:

If you test it with std::less you can get false positives.

Please forgive me for continuing further down this road and for being OT. But I don't understand how the std::less approach would give false positives. Care to explain, or direct me to a better location for getting the answer? Regards, Anders Dalvander -- WWFSMD?