[9fans] subtracting pointers on amd64 6c

[9fans] subtracting pointers on amd64 6c

[cinap_lenrek]

in the function /sys/src/cmd/cc/sub.c:/^arith we emit code
that cast the 64-bit subtraction result to 32-bit LONG *before*
doing the division of the sizeof of the pointer type.

so when the pointers are more than 4gb apart, we will calculate
the wrong result, even tho the result would have fit into a
32-bit LONG *after* the division.

questions:

1) why do we cast to long?
2) if a pointer subtraction has to yield a long, why dont we cast *after* the division?

	if(n->op == OSUB)
	if(i == TIND && j == TIND) {
		w = n->right->type->link->width;
		if(w < 1 || n->left->type->link == T || n->left->type->link->width < 1)
			goto bad;
		n->type = types[ewidth[TIND] <= ewidth[TLONG]? TLONG: TVLONG];
		if(1 && ewidth[TIND] > ewidth[TLONG]){	<------- here
			n1 = new1(OXXX, Z, Z);
			*n1 = *n;
			n->op = OCAST;
			n->left = n1;
			n->right = Z;
			n->type = types[TLONG];
		}
		if(w > 1) {
			n1 = new1(OXXX, Z, Z);
			*n1 = *n;
			n->op = ODIV;
			n->left = n1;
			n1 = new1(OCONST, Z, Z);
			n1->vconst = w;
			n1->type = n->type;
			n->right = n1;
			w = vlog(n1);
			if(w >= 0) {
				n->op = OASHR;
				n1->vconst = w;
			}
		}
		return;
	}

--
cinap

Re: [9fans] subtracting pointers on amd64 6c

[cinap_lenrek]

rsc has fixed this in the go 6c compiler. so far most code
seems to compile and work fine. the most fallout is with
warnings for %ld format strings as char* - char* is now
vlong instead of long.

is there any prefered way on how to move forwards with amd64?

i think as memories grow, we will hit problems with 32 bit
longs more often, so this change might be worthwhile in the
long term, even if having to add casts for print statements
is a bit annoying.

--
cinap

Re: [9fans] subtracting pointers on amd64 6c

[Charles Forsyth]

[-- Attachment #1: Type: text/plain, Size: 606 bytes --]

On 5 January 2016 at 06:36, <cinap_lenrek@felloff.net> wrote:

> 1) why do we cast to long?
>

because that's the type all existing code expected, and there wasn't much
application
for > 4gb in single arrays at the time (as opposed to having big memory in
big address spaces)


> 2) if a pointer subtraction has to yield a long, why dont we cast *after*
> the division?
>

 that would be certainly be better.

having said that, because of caching effects, especially on NUMA, it's
worth looking at data structures that
big to decide whether they might be better organised less naively.

[-- Attachment #2: Type: text/html, Size: 1230 bytes --]

Re: [9fans] subtracting pointers on amd64 6c

[Charles Forsyth]

[-- Attachment #1: Type: text/plain, Size: 289 bytes --]

On 5 January 2016 at 07:53, <cinap_lenrek@felloff.net> wrote:

> rsc has fixed this in the go 6c compiler. so far most code
> seems to compile and work fine. the most fallout is with
>

long x = p - q;
T *y = p+x;

really there needs to be a new typedef for the difference type.

[-- Attachment #2: Type: text/html, Size: 732 bytes --]

Re: [9fans] subtracting pointers on amd64 6c

[Charles Forsyth]

[-- Attachment #1: Type: text/plain, Size: 563 bytes --]

On 5 January 2016 at 10:15, Charles Forsyth <charles.forsyth@gmail.com>
wrote:

> 2) if a pointer subtraction has to yield a long, why dont we cast *after*
>> the division?
>>
>
>  that would be certainly be better.
>

since 6c is more commonly used now, and there's more interest or need, it's
probably best just to introduce
the difference type and change the result type. it's the same thing with
usize.
i'll see if i can add some code to check for mismatches automatically.

there are usable ANSI formats for the difference and sizeof types.

[-- Attachment #2: Type: text/html, Size: 1243 bytes --]

Re: [9fans] subtracting pointers on amd64 6c

[Devon H. O'Dell]

2016-01-05 2:28 GMT-08:00 Charles Forsyth <charles.forsyth@gmail.com>:
> since 6c is more commonly used now, and there's more interest or need, it's
> probably best just to introduce
> the difference type and change the result type. it's the same thing with
> usize.

i get that probably nobody cares about c standards here, but it might
be useful to mention what c99 and c11 say about this issue, since the
behavior is well-defined for every other c implementation (and minus
having a ptrdiff_t type, there's actually nothing wrong with the
current behavior). the latest particulars in c11 defining ptrdiff_t
and pointer addition and subtraction are at
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf page 93.
ptrdiff_t was introduced in c99.

the type specifies behavior of pointer subtraction where the pointers
point to elements within an array object. the size of this type is
implementation defined. when the pointers are not both pointer to
members of the same array object (or one past it), or when the
difference of the subtraction falls out of the range of the
implementation's ptrdiff_t type, the behavior is undefined. i think
practically, this means that the behavior is undefined if the pointers
belong to two separate memory allocations since variable-length arrays
are array objects *and* are dynamically allocated -- so this isn't
making a strong statement that the pointers have to be inside
something declared `T foo[N]`, but it is making a statement that they
have to be inside or one past a contiguous memory region of the same
type (and could alias).

so given any of the examples in this thread, if you typedef'ed
ptrdiff_t to long, then the compiler technically isn't actually doing
anything wrong. whether it is doing something useful is a different
question.

for practical purposes, if the compiler learned about a ptrdiff_t type
(or whatever you feel like calling it), and that type was 64 bits, it
would be enough to represent the difference between any two physical
addresses that amd64 could represent. for instance, although the range
of subtraction is theoretically -2^64+1 to 2^64-1, amd64 can only
address 48 bits of memory (currently) despite using 64 bits to
represent addresses. as long as virtual addresses in the system aren't
exabytes apart, this shouldn't result in undefined behavior in
practice.

Re: [9fans] subtracting pointers on amd64 6c

[Charles Forsyth]

[-- Attachment #1: Type: text/plain, Size: 1111 bytes --]

On 5 January 2016 at 19:01, Devon H. O'Dell <devon.odell@gmail.com> wrote:

> so given any of the examples in this thread, if you typedef'ed
> ptrdiff_t to long, then the compiler technically isn't actually doing
> anything wrong. whether it is doing something useful is a different
> question.
>

Well, although I knew that was true, I didn't want to push the point because
in practice, people have a right to expect certain reasonable behaviour,
and it's quite reasonable to expect that p+(q-p) yields q if they both point
into the same array that the system agreed to allocate somehow.
It make sense to use 64 bits for the difference, and indeed the code
block that adds the current cast has an if(1 && ...) suggesting an if(0 &&
...
to be inserted instead. It would have been better if I'd simply named it by
enum and
added a comment to explain some of this.

There are some effects on library interfaces that I didn't mention earlier,
but
since 64-bit operation should now be as common as not (allowing for 32-bit
ARM),
it makes sense to update everything to cope with it properly.

[-- Attachment #2: Type: text/html, Size: 1826 bytes --]

Re: [9fans] subtracting pointers on amd64 6c

[erik quanstrom]

On Tue Jan  5 11:49:06 PST 2016, charles.forsyth@gmail.com wrote:

> On 5 January 2016 at 19:01, Devon H. O'Dell <devon.odell@gmail.com> wrote:
>
> > so given any of the examples in this thread, if you typedef'ed
> > ptrdiff_t to long, then the compiler technically isn't actually doing
> > anything wrong. whether it is doing something useful is a different
> > question.
> >
>
> Well, although I knew that was true, I didn't want to push the point because
> in practice, people have a right to expect certain reasonable behaviour,
> and it's quite reasonable to expect that p+(q-p) yields q if they both point
> into the same array that the system agreed to allocate somehow.
> It make sense to use 64 bits for the difference, and indeed the code
> block that adds the current cast has an if(1 && ...) suggesting an if(0 &&

yes!  this.  one thing i love about the plan 9 compilers is that my reasonable
expectations are not violated by some happy optimizer, or decision.

this gets us back to the op's pov

> i get that probably nobody cares about c standards here, but it might
> be useful to mention what c99 and c11 say about this issue, since the

which i think is wrong.  there is some current silliness with compilers that
conflates allowed with required and undefined with can be deleted.  i
see plan 9's decisions as rejecting this way of thinking.  however, this is
in no way anti-standard.

- erik

Re: [9fans] subtracting pointers on amd64 6c

[erik quanstrom]

> since 6c is more commonly used now, and there's more interest or need,
> it's probably best just to introduce the difference type and change
> the result type.  it's the same thing with usize.  i'll see if i can
> add some code to check for mismatches automatically.
>
> there are usable ANSI formats for the difference and sizeof types.

i'm using usize, and its print modifier 'z' in 9atom.
i haven't added 't' for ptrdiff, since it doesn't exist in the compilers.

- erik

Re: [9fans] subtracting pointers on amd64 6c

[Devon H. O'Dell]

2016-01-05 12:40 GMT-08:00 erik quanstrom <quanstro@quanstro.net>:
> On Tue Jan  5 11:49:06 PST 2016, charles.forsyth@gmail.com wrote:
>
>> On 5 January 2016 at 19:01, Devon H. O'Dell <devon.odell@gmail.com> wrote:
>>
>> > so given any of the examples in this thread, if you typedef'ed
>> > ptrdiff_t to long, then the compiler technically isn't actually doing
>> > anything wrong. whether it is doing something useful is a different
>> > question.
>> >
>>
>> Well, although I knew that was true, I didn't want to push the point because
>> in practice, people have a right to expect certain reasonable behaviour,
>> and it's quite reasonable to expect that p+(q-p) yields q if they both point
>> into the same array that the system agreed to allocate somehow.
>> It make sense to use 64 bits for the difference, and indeed the code
>> block that adds the current cast has an if(1 && ...) suggesting an if(0 &&
>
> yes!  this.  one thing i love about the plan 9 compilers is that my reasonable
> expectations are not violated by some happy optimizer, or decision.

for reference, i said, "technically [the plan 9 compiler] isn't
actually doing anything wrong. whether it is doing something useful is
a different question." so far, we're all in agreement.

> this gets us back to the op's pov

how? it really doesn't, because you've misunderstood me apparently
based on understanding me through charles' reply...

>> i get that probably nobody cares about c standards here, but it might
>> be useful to mention what c99 and c11 say about this issue, since the

...and are now bringing up the one sentence of my post that has the
least meaning or relevance for this discussion...

> which i think is wrong.  there is some current silliness with compilers that
> conflates allowed with required and undefined with can be deleted.  i
> see plan 9's decisions as rejecting this way of thinking.  however, this is
> in no way anti-standard.

...and arguing with it, based on assuming charles is disagreeing with
me about reasonable behavior. he isn't. apparently, you didn't take
the time to read what i had written in the first place. or at least
not past the first sentence.

this is really annoying to me because it tends to be a frequent thing
you do when replying to me on this list: disagreeing with me based on
something that seems like either assuming i don't have any basis for
understanding what i'm talking about, or not reading what i've written
and assuming others are disagreeing with me. the reason this is
annoying is because i have to re-read what i've written, carefully, to
make sure i don't have to retract anything i've said.

in this case i don't. you seem to agree with everything i've said,
except for further misinterpreting a point about the compilers being
"anti-standard" and somehow correlating this statement to other
compilers (which I didn't talk about at all) and undefined behavior.

to be clear, in C, undefined behavior means the compiler can do
anything it likes at all, whether that is some compiler removing an
entire conditional body because it relies on signed integer overflow,
optimizing a loop to a memcpy because of strict aliasing, or plan 9
doing something in some case that you like. i haven't mentioned any
compilers or what they do with any undefined behavior in my original
post, only the spec, so it seems odd that you're going to disagree
with me based on stuff i didn't actually say.

furthermore,  the only undefined behavior i mentioned was what happens
when the difference between two pointers exceeds the width of the
ptrdiff type. this undefined behavior is still possible with a 64-bit
ptrdiff type. which would have been obvious if you actually read what
i said, instead of assuming charles was disagreeing with me (he
wasn't). so nothing about anything i said had anything to do with
undefined behavior other than to note that if plan 9's ptrdiff type is
long (which is allowed because impl. defined), then the behavior is
correct. and immediately after that, i said that's not useful
behavior.

all charles was saying was that he didn't mention any of this because
whether or not the behavior is correct per spec, it is not useful. and
the part that can be changed to be useful actually falls within
implementation-defined behavior. (which further makes your complaints
about compiler "silliness" with UB irrelevant, since nobody is talking
about UB at all).

finally, when i say "i get that probably nobody cares about c
standards here", it's because there are plenty of differences between
plan 9 c and any current c standard (or even ansi c). presenting the
standard as an argument to change the compiler is therefore unlikely
to hold any weight. there's a reason that plenty of c99 and c11 is
neither supported, nor intended to be supported by anybody on this
list, and it's not just because nobody cares enough to implement it.

but since i've written more than 2 sentences, i'm sure you'll find
plenty more to disagree with me on, especially in the infinite
sentences i didn't write.

Re: [9fans] subtracting pointers on amd64 6c

[cinap_lenrek]

> there are usable ANSI formats for the difference and sizeof types.

so one would write %td instead of %ld for ptrdiff type? that seems
easy.

i'm not so sure how usize/ssize would work. %zud and %zd? or would
the z flag imply unsigned? would the return type of sizeof() also
become usize?

--
cinap

Re: [9fans] subtracting pointers on amd64 6c

[Devon H. O'Dell]

2016-01-05 14:32 GMT-08:00  <cinap_lenrek@felloff.net>:
>> there are usable ANSI formats for the difference and sizeof types.
>
> so one would write %td instead of %ld for ptrdiff type? that seems
> easy.

yes, and there's support for u/i/o/X/x/etc modifiers

> i'm not so sure how usize/ssize would work. %zud and %zd? or would
> the z flag imply unsigned? would the return type of sizeof() also
> become usize?

it depends on what you are trying to target. that's why i bring up
standards as soon as you start talking about this. size_t and
ptrdiff_t are part of C. ssize_t isn't.

ssize_t is a posix-ism and is defined to store "values at least in the
range [-1, {SSIZE_MAX}]". If you care about what C says, then you can
do anything you want with ssize, because it isn't part of C. For
printing, %zu is size_t (per C) and %zd is ssize_t (per POSIX).

--dho

> --
> cinap
>

Re: [9fans] subtracting pointers on amd64 6c

[erik quanstrom]

On Tue Jan  5 14:34:52 PST 2016, cinap_lenrek@felloff.net wrote:
> > there are usable ANSI formats for the difference and sizeof types.
>
> so one would write %td instead of %ld for ptrdiff type? that seems
> easy.

yup.

> i'm not so sure how usize/ssize would work. %zud and %zd? or would
> the z flag imply unsigned? would the return type of sizeof() also
> become usize?

yes.  (but ssize doesn't exist yet.)

- erik

Re: [9fans] subtracting pointers on amd64 6c

[Devon H. O'Dell]

2016-01-05 14:57 GMT-08:00 Devon H. O'Dell <devon.odell@gmail.com>:
> 2016-01-05 14:32 GMT-08:00  <cinap_lenrek@felloff.net>:
>>> there are usable ANSI formats for the difference and sizeof types.
>>
>> so one would write %td instead of %ld for ptrdiff type? that seems
>> easy.
>
> yes, and there's support for u/i/o/X/x/etc modifiers
>
>> i'm not so sure how usize/ssize would work. %zud and %zd? or would
>> the z flag imply unsigned? would the return type of sizeof() also
>> become usize?
>
> it depends on what you are trying to target. that's why i bring up
> standards as soon as you start talking about this. size_t and
> ptrdiff_t are part of C. ssize_t isn't.
>
> ssize_t is a posix-ism and is defined to store "values at least in the
> range [-1, {SSIZE_MAX}]". If you care about what C says, then you can
> do anything you want with ssize, because it isn't part of C. For
> printing, %zu is size_t (per C) and %zd is ssize_t (per POSIX).

I'm wrong here, %z is for size_t in general (plus modifiers including d).

> --dho
>
>> --
>> cinap
>>

Re: [9fans] subtracting pointers on amd64 6c

[erik quanstrom]

> ...and arguing with it, based on assuming charles is disagreeing with
> me about reasonable behavior. he isn't. apparently, you didn't take
> the time to read what i had written in the first place. or at least
> not past the first sentence.
>
> this is really annoying to me because it tends to be a frequent thing
> you do when replying to me on this list: disagreeing with me based on
> something that seems like either assuming i don't have any basis for
> understanding what i'm talking about, or not reading what i've written
> and assuming others are disagreeing with me. the reason this is
> annoying is because i have to re-read what i've written, carefully, to
> make sure i don't have to retract anything i've said.

for the record, i did not intend to disagree with your statement.

i did want to make it clear that i, and several people i've worked with
on plan 9 have made a concerted effort to be as compliant with the
standard as reasonable; i was making a related by separate point.  etc.

sorry if you took it this way.  sorry for using your statement as a foil.
please accept my apology.

- erik

Re: [9fans] subtracting pointers on amd64 6c

[Dave Eckhardt]

> for instance, although the range of subtraction is theoretically
> -2^64+1 to 2^64-1, amd64 can only address 48 bits of memory
> (currently) despite using 64 bits to represent addresses.  as long
> as virtual addresses in the system aren't exabytes apart, this
> shouldn't result in undefined behavior in practice.

Unfortunately AMD64 VM is a hack.  The 2^48 addressable bytes aren't
contiguous!  2^47 of them go up from 0 and the other 2^47 of them go
down from (64-bit) -1.

See: https://en.wikipedia.org/wiki/X86-64#Canonical_form_addresses

Dave Eckhardt

Re: [9fans] subtracting pointers on amd64 6c

[cinap_lenrek]

it appears that %t and %z are already used by a bunch of programs,
including the kernel:

term% grep -n 'fmtinstall\(''[zt]''' */*.c */*/*.c */*/*/*.c
cmd/trace.c:137: 	fmtinstall('t', timeconv);
9/port/edf.c:122: 		fmtinstall('t', timeconv);
cmd/db/output.c:159: 	fmtinstall('t', tconv);
cmd/vac/unvac.c:45: 	fmtinstall('t', mtimefmt);
cmd/venti/srv/fixarenas.c:1897: 	fmtinstall('z', zfmt);
cmd/venti/srv/fixarenas.c:1898: 	fmtinstall('t', tfmt);

--
cinap

Re: [9fans] subtracting pointers on amd64 6c

[erik quanstrom]

On Tue Jan  5 23:02:59 PST 2016, cinap_lenrek@felloff.net wrote:
> it appears that %t and %z are already used by a bunch of programs,
> including the kernel:
>
> term% grep -n 'fmtinstall\(''[zt]''' */*.c */*/*.c */*/*/*.c
> cmd/trace.c:137: 	fmtinstall('t', timeconv);
> 9/port/edf.c:122: 		fmtinstall('t', timeconv);
> cmd/db/output.c:159: 	fmtinstall('t', tconv);
> cmd/vac/unvac.c:45: 	fmtinstall('t', mtimefmt);
> cmd/venti/srv/fixarenas.c:1897: 	fmtinstall('z', zfmt);
> cmd/venti/srv/fixarenas.c:1898: 	fmtinstall('t', tfmt);
>

yes, i changed fixarena's 'z' to 'Z'.  when necessary, i plan on changing
't' to 'T' or similar hopefully well-chosen non-conflicting character.

- erik

Re: [9fans] subtracting pointers on amd64 6c

[cinap_lenrek]

what if we introduce signed intptr type and use that instead
of introducing ptrdiff? ape already has a signed intptr_t
type.

then use 'z' as a modifier to mean "intptr size" so that
%zd would print signed intptr and %zud is for uintptr?

the %t and %T space seems rather crowded...

term% grep 'fmtinstall\(''[zZtT]' */*.c */*/*.c */*/*/*.c */*/*/*/*.c
cmd/timepic.c:	fmtinstall('T', Tfmt);
cmd/trace.c:	fmtinstall('t', timeconv);
libhtml/lex.c:	fmtinstall('T', Tconv);
libmach/kdb.c:		fmtinstall('T', Tfmt);
libmach/udb.c:		fmtinstall('T', Tfmt);
libventi/log.c:		fmtinstall('T', timefmt);
9/mtx/pci.c:	fmtinstall('T', tbdffmt);
9/pc/pci.c:	fmtinstall('T', tbdffmt);
9/port/edf.c:		fmtinstall('t', timeconv);
9/teg2/pci.c:	fmtinstall('T', tbdffmt);
cmd/cc/lex.c:	fmtinstall('T', Tconv);
cmd/cwfs/sub.c:	fmtinstall('Z', Zfmt);	/* print devices */
cmd/cwfs/sub.c:	fmtinstall('T', Tfmt);	/* print times */
cmd/db/output.c:	fmtinstall('t', tconv);
cmd/disk/rd9660.c:	fmtinstall('T', asciiTfmt);
cmd/disk/rd9660.c:	fmtinstall('T', runeTfmt);
cmd/hjfs/buf.c:	fmtinstall('T', Tfmt);
cmd/vac/unvac.c:	fmtinstall('t', mtimefmt);
cmd/upas/fs/imap4.c:	fmtinstall('Z', doublequote);
cmd/upas/marshal/marshal.c:	fmtinstall('Z', doublequote);
cmd/venti/srv/fixarenas.c:	fmtinstall('z', zfmt);
cmd/venti/srv/fixarenas.c:	fmtinstall('t', tfmt);
cmd/venti/srv/utils.c:	fmtinstall('T', vttimefmt);

--
cinap

Re: [9fans] subtracting pointers on amd64 6c

[erik quanstrom]

> the %t and %T space seems rather crowded...

i agree.  but %t is the real issue, and i see just 9 instances of that.
only one of them (the kernel) uses both %t and %T.  this seems easy
enough to fix.

for all but the kernel we can change %t to %T, and for the kernel
we'll have to use something odd.

i'll post a potential comprehensive solution to this this weekend.

- erik

---

 ; g 'fmtinstall[ 	]*\([ 	]*''[t]''' .
./9/port/edf.c:122: 		fmtinstall('t', timeconv);
./cmd/db/output.c:159: 	fmtinstall('t', tconv);
./cmd/ndb/tozone.c:797: 	fmtinstall('t', fmttabpad);
./cmd/trace.c:138: 	fmtinstall('t', timeconv);
./cmd/vac/unvac.c:45: 	fmtinstall('t', mtimefmt);
./cmd/venti/srv/fixarenas.c:1898: 	fmtinstall('t', tfmt);
./fs/port/sub.c:802: 	fmtinstall('t', tfmt);	/* print times */
./nix/port/edf.c:116: 		fmtinstall('t', timeconv);