Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #402780 > unrolled thread
| Started by | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| First post | 2026-10-06 23:08 -0700 |
| Last post | 2026-10-13 03:52 -0700 |
| Articles | 9 on this page of 89 — 19 participants |
Back to article view | Back to comp.lang.c
AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-06 23:08 -0700
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-07 15:25 +0200
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-07 12:13 -0700
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-07 21:28 +0200
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 05:31 -0700
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 11:12 +0200
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 11:12 +0200
Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-07 20:10 -0500
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 05:56 -0700
Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-08 15:09 -0500
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-08 22:56 +0200
Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-08 17:29 -0500
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 09:56 +0200
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 01:39 +0200
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-09 00:03 -0700
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 23:53 -0700
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 10:34 +0200
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 12:27 +0200
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 12:59 +0200
Re: AVL tree insertion - programming exercise bart <bc@freeuk.com> - 2026-10-09 11:43 +0100
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 13:20 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 12:38 +0000
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 16:05 +0200
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 17:54 +0200
Re: AVL tree insertion - programming exercise Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-10-10 10:38 +0800
Re: AVL tree insertion - programming exercise ram@zedat.fu-berlin.de (Stefan Ram) - 2026-10-10 03:12 +0000
Re: AVL tree insertion - programming exercise Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-10-10 04:44 +0000
Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-10 14:12 -0700
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 19:48 +0000
Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-09 23:18 +0000
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 15:27 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-12 18:26 +0000
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-12 21:17 +0200
Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-09 17:47 +0300
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 16:48 +0000
Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 19:08 +0300
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 18:29 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:44 +0000
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 23:22 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:43 +0000
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 20:35 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 19:36 +0000
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 22:08 +0200
Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:21 +0300
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 20:55 +0000
Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-10 20:22 +0000
Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:32 +0300
Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-11 15:24 +0000
Re: AVL tree insertion - programming exercise Bonita Montero <Bonita.Montero@gmail.com> - 2026-10-10 19:40 +0200
Re: AVL tree insertion - programming exercise Andrey Tarasevich <noone@noone.net> - 2026-10-10 12:39 -0700
Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:00 +0300
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 22:28 +0200
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-10 19:02 -0700
Re: AVL tree insertion - programming exercise "chine.bleu" <chine.bleu@yahoo.com> - 2026-10-13 01:38 -0700
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-13 11:42 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 10:55 +0000
Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 04:29 -0700
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-13 14:01 +0200
Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 05:09 -0700
Re: AVL tree insertion - programming exercise antispam@fricas.org (Waldek Hebisch) - 2026-10-13 19:01 +0000
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 15:17 +0000
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-13 17:39 +0200
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-13 09:01 -0700
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 21:17 +0000
Re: AVL tree insertion - programming exercise "chine.bleu" <chine.bleu@yahoo.com> - 2026-10-13 18:01 -0700
Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 21:13 -0700
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-14 09:43 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-14 20:11 +0000
Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-14 15:25 -0700
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-15 09:28 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-14 14:13 +0000
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-14 18:03 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-14 18:21 +0000
Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-14 15:42 -0700
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-15 14:25 +0000
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-14 10:39 -0700
Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-13 17:15 +0000
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 21:30 +0000
Re: AVL tree insertion - programming exercise "chine.bleu" <chine.bleu@yahoo.com> - 2026-10-13 08:19 -0700
Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-13 13:16 -0700
Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-13 23:28 +0300
Re: AVL tree insertion - programming exercise James Kuyper <jameskuyper@alumni.caltech.edu> - 2026-10-13 06:20 -0400
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 14:34 +0000
Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 20:45 -0700
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-14 14:25 +0000
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-14 20:54 -0700
Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-14 22:47 -0700
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-15 04:42 -0700
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-13 03:52 -0700
Page 5 of 5 — ← Prev page 1 2 3 4 [5]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-10-13 23:28 +0300 |
| Message-ID | <20261013232832.0000725b@yahoo.com> |
| In reply to | #403121 |
On Tue, 13 Oct 2026 13:16:44 -0700 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wrote: > > Oh shit! I cannot get into google groups, I get a god damn: 429 Too > Many Requests You can get into google groups but you would have to do it manually, step by step starting from top https://groups.google.com Shortcuts, even the simplest ones like https://groups.google.com/g/comp.lang.c nowadays work very rarely. So it goes.
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2026-10-13 06:20 -0400 |
| Message-ID | <11al0l0$eefv$1@dont-email.me> |
| In reply to | #403084 |
On 13/10/2026 10:38, chine.bleu wrote: ...> As a precaution check the return > address of malloc > > p = malloc(m); > if ((uintptr_t)p)&1!=0) abort(); Just to be pedantic, the standard doesn't guarantee that the expression you use will test what you want to test. Since there is a guarantee that malloc() returns a universally aligned memory, I think it's actually more likely that the test will fail than that malloc() will fail, though both probabilities are quite negligible, so it's hard to be sure.
[toc] | [prev] | [next] | [standalone]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2026-10-13 14:34 +0000 |
| Message-ID | <11alfgs$t7q$1@reader2.panix.com> |
| In reply to | #403089 |
In article <11al0l0$eefv$1@dont-email.me>, James Kuyper <jameskuyper@alumni.caltech.edu> wrote: >On 13/10/2026 10:38, chine.bleu wrote: >...> As a precaution check the return >> address of malloc >> >> p = malloc(m); >> if ((uintptr_t)p)&1!=0) abort(); > >Just to be pedantic, the standard doesn't guarantee that the expression >you use will test what you want to test. Since there is a guarantee that >malloc() returns a universally aligned memory, I think it's actually >more likely that the test will fail than that malloc() will fail, though >both probabilities are quite negligible, so it's hard to be sure. The syntax and precedence errors aside, the test is clearly meant to ensure that the low bit in the return from `malloc` is clear, so that it can be repurposed for other things. It should likely be: p = malloc(m); if (p == NULL || ((uintptr_t)p & 1) != 0) abort(); - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <Keith.S.Thompson+u@gmail.com> |
|---|---|
| Date | 2026-10-13 20:45 -0700 |
| Message-ID | <11amttk$14pou$2@kst.eternal-september.org> |
| In reply to | #403103 |
cross@spitfire.i.gajendra.net (Dan Cross) writes:
> In article <11al0l0$eefv$1@dont-email.me>,
> James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>On 13/10/2026 10:38, chine.bleu wrote:
>>...> As a precaution check the return
>>> address of malloc
>>>
>>> p = malloc(m);
>>> if ((uintptr_t)p)&1!=0) abort();
>>
>>Just to be pedantic, the standard doesn't guarantee that the expression
>>you use will test what you want to test. Since there is a guarantee that
>>malloc() returns a universally aligned memory, I think it's actually
>>more likely that the test will fail than that malloc() will fail, though
>>both probabilities are quite negligible, so it's hard to be sure.
>
> The syntax and precedence errors aside, the test is clearly
> meant to ensure that the low bit in the return from `malloc` is
> clear, so that it can be repurposed for other things. It should
> likely be:
>
> p = malloc(m);
> if (p == NULL || ((uintptr_t)p & 1) != 0) abort();
I'm not sure the NULL test adds anything useful. The low-order bits of
a null pointer are very likely to be 0 on any real-world system.
Also, the test only looks at the low-order bits of the result of
the current malloc() call. If you have an exotic system where
an aligned pointer can have a low-order bit set to 1, it might
*sometimes* be set to 0.
--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */
[toc] | [prev] | [next] | [standalone]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2026-10-14 14:25 +0000 |
| Message-ID | <11ao3dn$8hr$1@reader2.panix.com> |
| In reply to | #403140 |
In article <11amttk$14pou$2@kst.eternal-september.org>, Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote: >cross@spitfire.i.gajendra.net (Dan Cross) writes: >> In article <11al0l0$eefv$1@dont-email.me>, >> James Kuyper <jameskuyper@alumni.caltech.edu> wrote: >>>On 13/10/2026 10:38, chine.bleu wrote: >>>...> As a precaution check the return >>>> address of malloc >>>> >>>> p = malloc(m); >>>> if ((uintptr_t)p)&1!=0) abort(); >>> >>>Just to be pedantic, the standard doesn't guarantee that the expression >>>you use will test what you want to test. Since there is a guarantee that >>>malloc() returns a universally aligned memory, I think it's actually >>>more likely that the test will fail than that malloc() will fail, though >>>both probabilities are quite negligible, so it's hard to be sure. >> >> The syntax and precedence errors aside, the test is clearly >> meant to ensure that the low bit in the return from `malloc` is >> clear, so that it can be repurposed for other things. It should >> likely be: >> >> p = malloc(m); >> if (p == NULL || ((uintptr_t)p & 1) != 0) abort(); > >I'm not sure the NULL test adds anything useful. The low-order bits of >a null pointer are very likely to be 0 on any real-world system. It was just meant to `abort` if `malloc` could not allocate for whatever reason, and was unrelated to this business of stealing low bits to cache other data. The assertion is that, if the program survives these tests, then `p` is suitable for use. Sorry, I should have been clear about that. >Also, the test only looks at the low-order bits of the result of >the current malloc() call. If you have an exotic system where >an aligned pointer can have a low-order bit set to 1, it might >*sometimes* be set to 0. I think the point is that if one wants to repurpose the low bits of the integer representation of `p` for some purpose, then one ought to verify the base assumption that those bits are available. One need not do that on every malloc call, however. In the face of weird implementations and esoteric hardware, I don't know that one can have a more general test suitable for e.g. a `static_assert()`. - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-10-14 20:54 -0700 |
| Message-ID | <86se27r52l.fsf@linuxsc.com> |
| In reply to | #403140 |
Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>
>> In article <11al0l0$eefv$1@dont-email.me>,
>> James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>
>>> On 13/10/2026 10:38, chine.bleu wrote:
>>> ...> As a precaution check the return
>>>
>>>> address of malloc
>>>>
>>>> p = malloc(m);
>>>> if ((uintptr_t)p)&1!=0) abort();
>>>
>>> Just to be pedantic, the standard doesn't guarantee that the
>>> expression you use will test what you want to test. Since there
>>> is a guarantee that malloc() returns a universally aligned memory,
>>> I think it's actually more likely that the test will fail than
>>> that malloc() will fail, though both probabilities are quite
>>> negligible, so it's hard to be sure.
>>
>> The syntax and precedence errors aside, the test is clearly
>> meant to ensure that the low bit in the return from `malloc` is
>> clear, so that it can be repurposed for other things. It should
>> likely be:
>>
>> p = malloc(m);
>> if (p == NULL || ((uintptr_t)p & 1) != 0) abort();
>
> I'm not sure the NULL test adds anything useful. The low-order bits
> of a null pointer are very likely to be 0 on any real-world system.
Surely we would like to protect against a null pointer being used
to access a non-existent object.
> Also, the test only looks at the low-order bits of the result of
> the current malloc() call. If you have an exotic system where
> an aligned pointer can have a low-order bit set to 1, it might
> *sometimes* be set to 0.
As long as the bit in question /is/ zero it doesn't matter if it
might have been one. The bit will always be cleared before using
the pointer as a pointer, so the pointer value in use will match
the pointer value originally returned.
Thus we might write a safe allocation function as follows:
void *
safe_new( size_t n ){
void *p = 0;
while( !p || (uintptr_t)p %2 != 0 ) free( p ), p = malloc( n++ );
return p;
}
Of course it might not succeed in some cases, but it will be
quite obvious if it doesn't. :)
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <Keith.S.Thompson+u@gmail.com> |
|---|---|
| Date | 2026-10-14 22:47 -0700 |
| Message-ID | <11appe9$24dl1$1@kst.eternal-september.org> |
| In reply to | #403174 |
Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>> In article <11al0l0$eefv$1@dont-email.me>,
>>> James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>>> On 13/10/2026 10:38, chine.bleu wrote:
>>>> ...> As a precaution check the return
>>>>
>>>>> address of malloc
>>>>>
>>>>> p = malloc(m);
>>>>> if ((uintptr_t)p)&1!=0) abort();
>>>>
>>>> Just to be pedantic, the standard doesn't guarantee that the
>>>> expression you use will test what you want to test. Since there
>>>> is a guarantee that malloc() returns a universally aligned memory,
>>>> I think it's actually more likely that the test will fail than
>>>> that malloc() will fail, though both probabilities are quite
>>>> negligible, so it's hard to be sure.
>>>
>>> The syntax and precedence errors aside, the test is clearly
>>> meant to ensure that the low bit in the return from `malloc` is
>>> clear, so that it can be repurposed for other things. It should
>>> likely be:
>>>
>>> p = malloc(m);
>>> if (p == NULL || ((uintptr_t)p & 1) != 0) abort();
>>
>> I'm not sure the NULL test adds anything useful. The low-order bits
>> of a null pointer are very likely to be 0 on any real-world system.
>
> Surely we would like to protect against a null pointer being used
> to access a non-existent object.
>
>> Also, the test only looks at the low-order bits of the result of
>> the current malloc() call. If you have an exotic system where
>> an aligned pointer can have a low-order bit set to 1, it might
>> *sometimes* be set to 0.
>
> As long as the bit in question /is/ zero it doesn't matter if it
> might have been one. The bit will always be cleared before using
> the pointer as a pointer, so the pointer value in use will match
> the pointer value originally returned.
>
> Thus we might write a safe allocation function as follows:
>
> void *
> safe_new( size_t n ){
> void *p = 0;
>
> while( !p || (uintptr_t)p %2 != 0 ) free( p ), p = malloc( n++ );
>
> return p;
> }
>
> Of course it might not succeed in some cases, but it will be
> quite obvious if it doesn't. :)
I might be missing the point of "chine.bleu"'s suggestion. I was
assuming that the point was to check whether it's possible *in
general* to play with the low-order bits of malloc'ed pointers.
On most systems, you can probably make that assumption based on
what you know about the system's memory model. But it can't be
checked reliably at run time.
If I wanted my program to play with low-order bits of pointers, and
refuse to run if the system doesn't support that, I might write a
program that does a *lot* of malloc() calls and invoke it during
configuration, refusing to proceed with the build if it reports that
malloc() can return an "odd" pointer. Aborting during execution
feels sloppy.
--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-10-15 04:42 -0700 |
| Message-ID | <86fqy7qjg2.fsf@linuxsc.com> |
| In reply to | #403176 |
Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>>
>>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>>
>>>> In article <11al0l0$eefv$1@dont-email.me>,
>>>> James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>>>
>>>>> On 13/10/2026 10:38, chine.bleu wrote:
>>>>> ...> As a precaution check the return
>>>>>
>>>>>> address of malloc
>>>>>>
>>>>>> p = malloc(m);
>>>>>> if ((uintptr_t)p)&1!=0) abort();
>>>>>
>>>>> Just to be pedantic, the standard doesn't guarantee that the
>>>>> expression you use will test what you want to test. Since there
>>>>> is a guarantee that malloc() returns a universally aligned memory,
>>>>> I think it's actually more likely that the test will fail than
>>>>> that malloc() will fail, though both probabilities are quite
>>>>> negligible, so it's hard to be sure.
>>>>
>>>> The syntax and precedence errors aside, the test is clearly
>>>> meant to ensure that the low bit in the return from `malloc` is
>>>> clear, so that it can be repurposed for other things. It should
>>>> likely be:
>>>>
>>>> p = malloc(m);
>>>> if (p == NULL || ((uintptr_t)p & 1) != 0) abort();
>>>
>>> I'm not sure the NULL test adds anything useful. The low-order bits
>>> of a null pointer are very likely to be 0 on any real-world system.
>>
>> Surely we would like to protect against a null pointer being used
>> to access a non-existent object.
>>
>>> Also, the test only looks at the low-order bits of the result of
>>> the current malloc() call. If you have an exotic system where
>>> an aligned pointer can have a low-order bit set to 1, it might
>>> *sometimes* be set to 0.
>>
>> As long as the bit in question /is/ zero it doesn't matter if it
>> might have been one. The bit will always be cleared before using
>> the pointer as a pointer, so the pointer value in use will match
>> the pointer value originally returned.
>>
>> Thus we might write a safe allocation function as follows:
>>
>> void *
>> safe_new( size_t n ){
>> void *p = 0;
>>
>> while( !p || (uintptr_t)p %2 != 0 ){
>> free( p ), p = malloc( n++ );
>> }
>>
>> return p;
>> }
>>
>> Of course it might not succeed in some cases, but it will be
>> quite obvious if it doesn't. :)
>
> I might be missing the point of "chine.bleu"'s suggestion. I was
> assuming that the point was to check whether it's possible *in
> general* to play with the low-order bits of malloc'ed pointers.
I took the tests with the abort() calls to be simply protection
against an unsuitable pointer being returned. Nothing more
complicated than that.
The point I was making is different. It doesn't matter if the
bit in question is always zero as long as it is zero a fair
amount of the time. Also it doesn't have to be a low order bit,
or any pre-chosen bit, as long as some particular bit is zero
often enough. We can imagine doing a lot of malloc() calls at
program startup and tallying how often a zero appears at each bit
position, and using one of the bit positions with a high count.
Simply do enough malloc() calls until the value returned has a
zero bit at the selected bit position. The code above looks at a
fixed low order bit, but it could just as well look at a bit
whose position was chosen at run time during program startup.
> On most systems, you can probably make that assumption based on
> what you know about the system's memory model. But it can't be
> checked reliably at run time.
>
> If I wanted my program to play with low-order bits of pointers, and
> refuse to run if the system doesn't support that, I might write a
> program that does a *lot* of malloc() calls and invoke it during
> configuration, refusing to proceed with the build if it reports that
> malloc() can return an "odd" pointer. Aborting during execution
> feels sloppy.
I understand what you're saying. It's mostly orthogonal to what
I was saying.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-10-13 03:52 -0700 |
| Message-ID | <86bj8xj2jk.fsf@linuxsc.com> |
| In reply to | #403084 |
"chine.bleu" <chine.bleu@yahoo.com> writes:
> Tim Rentsch wrote:
>
>> sons[2] array. These links are basically pointers, but held
>> as uintptr_t so they can take one of the bits to mean "tall",
>> which means taller than the other subtree of the node. The
>> tree structure should maintain an invariant that at most one
>
> Memory is cheap. Do not encode tags into low bits of an address unless
> you really know what your doing. As a precaution check the return
> address of malloc
>
> p = malloc(m);
> if ((uintptr_t)p)&1!=0) abort();
Yes, in general the interface described will fall down on some
systems. But it's just an exercise. Feel free to use code along
the lines of the following (disclaimer: not tested) to confirm
the suitability of the pointer values being used:
Node *
new_node( int key ){
Node *r = malloc( sizeof *r );
assert( (uintptr_t)r %2 ==0 );
*r = (Node){ .key = key };
return r;
}
[toc] | [prev] | [standalone]
Page 5 of 5 — ← Prev page 1 2 3 4 [5]
Back to top | Article view | comp.lang.c
csiph-web