GNU bug report logs - #75551
Potentially erroneous long loop in lrealloc

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 75551 in the body.
You can then email your comments to 75551 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Hong Xu <hong <at> topbug.net>
To: bug-gnu-emacs <bug-gnu-emacs <at> gnu.org>
Subject: Potentially erroneous long loop in lrealloc
Date: Mon, 13 Jan 2025 18:30:58 -0800

lrealloc has a loop that keeps checking alignment by calling laligned:

  while (true)
    {
      p = realloc (p, size);
      if (laligned (p, size) && (size || p))
	return p;
      size_t bigger = size + LISP_ALIGNMENT;
      if (size < bigger)
	size = bigger;
    }

Note that the loop increment size by LISP_ALIGNMENT each time if the
conditions are not satisfied.

One check in aligned is size % LISP_ALIGNMENT != 0:

static bool
laligned (void *p, size_t size)
{
  return (MALLOC_IS_LISP_ALIGNED || (intptr_t) p % LISP_ALIGNMENT == 0
	  || size % LISP_ALIGNMENT != 0);
}

Consider a host where MALLOC_IS_LISP_ALIGNED is false and p %
LISP_ALIGNMENT is frequently nonzero. if lrealloc is called with size
being a multiplier of LISP_ALIGNMENT, the loop can take a long time to
end until p % LISP_ALIGNMENT == 0, potentially until OOM.

Based on my understanding, this part is to address some "oddball" hosts
(based on the comment in alloc.c). But this does seem like a bug to me
if Emacs is running on such an oddball host...

-- 
Hong

Message #8 received at 75551 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Hong Xu <hong <at> topbug.net>, Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 75551 <at> debbugs.gnu.org
Subject: Re: bug#75551: Potentially erroneous long loop in lrealloc
Date: Tue, 14 Jan 2025 05:34:02 +0200

> From: Hong Xu <hong <at> topbug.net>
> Date: Mon, 13 Jan 2025 18:30:58 -0800
> 
> 
> lrealloc has a loop that keeps checking alignment by calling laligned:
> 
>   while (true)
>     {
>       p = realloc (p, size);
>       if (laligned (p, size) && (size || p))
> 	return p;
>       size_t bigger = size + LISP_ALIGNMENT;
>       if (size < bigger)
> 	size = bigger;
>     }
> 
> Note that the loop increment size by LISP_ALIGNMENT each time if the
> conditions are not satisfied.
> 
> One check in aligned is size % LISP_ALIGNMENT != 0:
> 
> static bool
> laligned (void *p, size_t size)
> {
>   return (MALLOC_IS_LISP_ALIGNED || (intptr_t) p % LISP_ALIGNMENT == 0
> 	  || size % LISP_ALIGNMENT != 0);
> }
> 
> Consider a host where MALLOC_IS_LISP_ALIGNED is false and p %
> LISP_ALIGNMENT is frequently nonzero. if lrealloc is called with size
> being a multiplier of LISP_ALIGNMENT, the loop can take a long time to
> end until p % LISP_ALIGNMENT == 0, potentially until OOM.
> 
> Based on my understanding, this part is to address some "oddball" hosts
> (based on the comment in alloc.c). But this does seem like a bug to me
> if Emacs is running on such an oddball host...

Paul, could you please comment on this?

Thanks.

Message #11 received at 75551 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Eli Zaretskii <eliz <at> gnu.org>, Hong Xu <hong <at> topbug.net>
Cc: 75551 <at> debbugs.gnu.org
Subject: Re: bug#75551: Potentially erroneous long loop in lrealloc
Date: Tue, 14 Jan 2025 13:04:49 -0800

On 2025-01-13 19:34, Eli Zaretskii wrote:
>> Consider a host where MALLOC_IS_LISP_ALIGNED is false and p %
>> LISP_ALIGNMENT is frequently nonzero. if lrealloc is called with size
>> being a multiplier of LISP_ALIGNMENT, the loop can take a long time to
>> end until p % LISP_ALIGNMENT == 0, potentially until OOM.
>>
>> Based on my understanding, this part is to address some "oddball" hosts
>> (based on the comment in alloc.c). But this does seem like a bug to me
>> if Emacs is running on such an oddball host...
> Paul, could you please comment on this?

As far as we know, there are no oddball hosts.

If Emacs is ever built on an oddball host, the code will operate 
correctly albeit possibly very inefficiently (perhaps including unwanted 
memory exhaustion).

Alternatively, the code could simply run emacs_abort() instead of 
retrying the allocation. There should be no difference on today's 
platforms so it's no big deal either way.

Or we could even remove the runtime test entirely, i.e., remove lrealloc 
and simply call realloc. That would make Emacs a bit faster in Lisp 
allocation.

Message #14 received at 75551 <at> debbugs.gnu.org (full text, mbox):

From: Hong Xu <hong <at> topbug.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 75551 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#75551: Potentially erroneous long loop in lrealloc
Date: Wed, 15 Jan 2025 16:11:07 -0800

On 2025-01-14 Tue 13:04 GMT-08, Paul Eggert <eggert <at> cs.ucla.edu> wrote:

> On 2025-01-13 19:34, Eli Zaretskii wrote:
>>> Consider a host where MALLOC_IS_LISP_ALIGNED is false and p %
>>> LISP_ALIGNMENT is frequently nonzero. if lrealloc is called with size
>>> being a multiplier of LISP_ALIGNMENT, the loop can take a long time to
>>> end until p % LISP_ALIGNMENT == 0, potentially until OOM.
>>>
>>> Based on my understanding, this part is to address some "oddball" hosts
>>> (based on the comment in alloc.c). But this does seem like a bug to me
>>> if Emacs is running on such an oddball host...
>> Paul, could you please comment on this?
>
> As far as we know, there are no oddball hosts.
>
> If Emacs is ever built on an oddball host, the code will operate correctly
> albeit possibly very inefficiently (perhaps including unwanted memory
> exhaustion).
>
> Alternatively, the code could simply run emacs_abort() instead of retrying the
> allocation. There should be no difference on today's platforms so it's no big
> deal either way.
>
> Or we could even remove the runtime test entirely, i.e., remove lrealloc and
> simply call realloc. That would make Emacs a bit faster in Lisp allocation.

It seems like the code is a bit less ideal to me -- on an imaginary
oddball host, this memory exhaustion bug is so frequent that I would
rather consider Emacs unsupported on such an oddball host.

I agree that it may be better to just remove lrealloc -- the memory
allocation code is so twisted that it can become a potential
hazard of security bugs on a normal host. We can add a compile time
check so that Emacs can't compile on an oddball host -- if there is
really one.

If an odd host indeed exists, I think the it's a simpler and cleaner
solution to replace the implementation of realloc with an aligned while
inefficient one, while keeping the logic of normal hosts intact.

What do you think?

-- 
Hong

Message #17 received at 75551 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Hong Xu <hong <at> topbug.net>
Cc: 75551 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#75551: Potentially erroneous long loop in lrealloc
Date: Wed, 15 Jan 2025 23:41:44 -0800

[Message part 1 (text/plain, inline)]

On 2025-01-15 16:11, Hong Xu wrote:
> It seems like the code is a bit less ideal to me -- on an imaginary
> oddball host, this memory exhaustion bug is so frequent that I would
> rather consider Emacs unsupported on such an oddball host.
> 
> I agree that it may be better to just remove lrealloc

Good points. Attached is a patch to make that change in a safe way. 
Please take a look at it and give it a try.

[0001-Simplify-alloc-by-assuming-MALLOC_IS_LISP_ALIGNED.patch (text/x-patch, attachment)]

Message #20 received at 75551 <at> debbugs.gnu.org (full text, mbox):

From: Hong Xu <hong <at> topbug.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 75551 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#75551: Potentially erroneous long loop in lrealloc
Date: Thu, 16 Jan 2025 13:46:53 -0800

On 2025-01-15 Wed 23:41 GMT-08, Paul Eggert <eggert <at> cs.ucla.edu> wrote:

> On 2025-01-15 16:11, Hong Xu wrote:
>> It seems like the code is a bit less ideal to me -- on an imaginary
>> oddball host, this memory exhaustion bug is so frequent that I would
>> rather consider Emacs unsupported on such an oddball host.
>> I agree that it may be better to just remove lrealloc
>
> Good points. Attached is a patch to make that change in a safe way. Please take
> a look at it and give it a try.

After applying the patch to the master branch, I'm getting a memory
exhaustion error when starting Emacs:

    $ ./src/temacs -Q
    emacs: memory exhausted

This is my backtrace:

#0  memory_full (nbytes=0) at ../../src/alloc.c:4319
#1  0x0000000000600854 in xrealloc (block=0x100f180, size=0) at ../../src/alloc.c:811
#2  0x00000000005e33cc in shrink_regexp_cache () at ../../src/search.c:150
#3  0x00000000006093f6 in garbage_collect () at ../../src/alloc.c:6526
#4  0x00000000006091a1 in maybe_garbage_collect () at ../../src/alloc.c:6442
#5  0x000000000063e2a6 in maybe_gc () at ../../src/lisp.h:5979
#6  0x0000000000645632 in Ffuncall (nargs=2, args=0x7fffffffacb0) at ../../src/eval.c:3077
#7  0x0000000000657397 in mapcar1 (leni=1472, vals=0x103eea0, fn=0x9f7c0, seq=0x8ccffb <pure+147227>) at ../../src/fns.c:3388
#8  0x000000000065789a in Fmapconcat (function=0x9f7c0, sequence=0x8ccffb <pure+147227>, separator=0x8a90e4 <pure+4>) at ../../src/fns.c:3475
#9  0x00000000006a604e in hash_native_abi () at ../../src/comp.c:798
#10 0x0000000000564adb in main (argc=2, argv=0x7fffffffb0a8) at ../../src/emacs.c:2499

Looks like realloc with size=0 need to be specifically handled as it
acts as freeing the memory and returns null.

-- 
Hong

Message #23 received at 75551 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Hong Xu <hong <at> topbug.net>
Cc: 75551 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#75551: Potentially erroneous long loop in lrealloc
Date: Thu, 16 Jan 2025 23:37:29 -0800

[Message part 1 (text/plain, inline)]

On 2025-01-16 13:46, Hong Xu wrote:
> After applying the patch to the master branch, I'm getting a memory
> exhaustion error when starting Emacs:

Oh, I was assuming sane malloc/realloc behavior and you tested on a 
platform which doesn't do that. Gnulib fixes that and I thought Emacs 
was already using Gnulib for this, but I now see that Emacs uses Gnulib 
to fix only malloc, not realloc.

Please try the attached two patches instead. The first one arranges for 
Emacs to also fix realloc. The second one is the same patch that I gave 
you earlier, the patch that simplifies the lrealloc code.

The MS-Windows port already fixes malloc and realloc in a different way, 
so the first patch should affect only non-MS-Windows platforms.

[0001-Let-Gnulib-deal-with-malloc-realloc-0.patch (text/x-patch, attachment)]

[0002-Simplify-alloc-by-assuming-MALLOC_IS_LISP_ALIGNED.patch (text/x-patch, attachment)]

Message #26 received at 75551 <at> debbugs.gnu.org (full text, mbox):

From: Hong Xu <hong <at> topbug.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 75551 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#75551: Potentially erroneous long loop in lrealloc
Date: Fri, 17 Jan 2025 13:05:36 -0800

On Thu 2025/01/16 23:37:29-0800 (PST), Paul Eggert wrote:
> On 2025-01-16 13:46, Hong Xu wrote:
>> After applying the patch to the master branch, I'm getting a memory
>> exhaustion error when starting Emacs:
> 
> Oh, I was assuming sane malloc/realloc behavior and you tested on a platform which doesn't do that. Gnulib fixes that and I thought Emacs was already using Gnulib for this, but I now see that Emacs uses Gnulib to fix only malloc, not realloc.
> 
> Please try the attached two patches instead. The first one arranges for Emacs to also fix realloc. The second one is the same patch that I gave you earlier, the patch that simplifies the lrealloc code.
> 
> The MS-Windows port already fixes malloc and realloc in a different way, so the first patch should affect only non-MS-Windows platforms.

Thanks, the patch looks good to me and works well on my host!

Message #29 received at 75551 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 75551 <at> debbugs.gnu.org, hong <at> topbug.net
Subject: Re: bug#75551: Potentially erroneous long loop in lrealloc
Date: Fri, 17 Jan 2025 23:07:50 +0200

> Date: Thu, 16 Jan 2025 23:37:29 -0800
> Cc: Eli Zaretskii <eliz <at> gnu.org>, 75551 <at> debbugs.gnu.org
> From: Paul Eggert <eggert <at> cs.ucla.edu>
> 
> The MS-Windows port already fixes malloc and realloc in a different way, 
> so the first patch should affect only non-MS-Windows platforms.

Since you add the realloc-posix module, it will need to be omitted on
MS-Windows.

Message #34 received at 75551-done <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Hong Xu <hong <at> topbug.net>
Cc: 75551-done <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#75551: Potentially erroneous long loop in lrealloc
Date: Fri, 17 Jan 2025 15:57:05 -0800

On 2025-01-17 13:05, Hong Xu wrote:
> Thanks, the patch looks good to me and works well on my host!

Thanks for checking. I installed it on the master branch and am marking 
this bug as done.

Message #37 received at 75551 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 75551 <at> debbugs.gnu.org, hong <at> topbug.net
Subject: Re: bug#75551: Potentially erroneous long loop in lrealloc
Date: Fri, 17 Jan 2025 15:58:38 -0800

On 2025-01-17 13:07, Eli Zaretskii wrote:
>> Date: Thu, 16 Jan 2025 23:37:29 -0800
>> Cc: Eli Zaretskii <eliz <at> gnu.org>, 75551 <at> debbugs.gnu.org
>> From: Paul Eggert <eggert <at> cs.ucla.edu>
>>
>> The MS-Windows port already fixes malloc and realloc in a different way,
>> so the first patch should affect only non-MS-Windows platforms.
> 
> Since you add the realloc-posix module, it will need to be omitted on
> MS-Windows.

I already did that in 2021 in commit 
1a65d49931ebc37adc48cd2406220b586e62f778, which added 
OMIT_GNULIB_MODULE_realloc-posix to nt/gnulib-cfg.mk. That line hasn't 
been needed for some time, but it'll be needed now that Emacs is using 
realloc-posix directly.

By the way, nt/gnulib-cfg.mk seems to contain some other 
OMIT_GNULIB_MODULE_* lines it no longer needs. A quick check suggests 
the following Gnulib modules have unnecessary lines like that. These 
unnecessary lines don't break builds of course.

float
fpucw   [probably a typo for fputcw but that isn't needed either]
fseterr
realloc-gnu
secure_getenv
signbit
size_max
stpncpy
xsize

Message #40 received at 75551 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 75551 <at> debbugs.gnu.org, hong <at> topbug.net
Subject: Re: bug#75551: Potentially erroneous long loop in lrealloc
Date: Sat, 18 Jan 2025 09:45:33 +0200

> Date: Fri, 17 Jan 2025 15:58:38 -0800
> Cc: hong <at> topbug.net, 75551 <at> debbugs.gnu.org
> From: Paul Eggert <eggert <at> cs.ucla.edu>
> 
> On 2025-01-17 13:07, Eli Zaretskii wrote:
> >> Date: Thu, 16 Jan 2025 23:37:29 -0800
> >> Cc: Eli Zaretskii <eliz <at> gnu.org>, 75551 <at> debbugs.gnu.org
> >> From: Paul Eggert <eggert <at> cs.ucla.edu>
> >>
> >> The MS-Windows port already fixes malloc and realloc in a different way,
> >> so the first patch should affect only non-MS-Windows platforms.
> > 
> > Since you add the realloc-posix module, it will need to be omitted on
> > MS-Windows.
> 
> I already did that in 2021 in commit 
> 1a65d49931ebc37adc48cd2406220b586e62f778, which added 
> OMIT_GNULIB_MODULE_realloc-posix to nt/gnulib-cfg.mk. That line hasn't 
> been needed for some time, but it'll be needed now that Emacs is using 
> realloc-posix directly.

Right, thanks.

> By the way, nt/gnulib-cfg.mk seems to contain some other 
> OMIT_GNULIB_MODULE_* lines it no longer needs. A quick check suggests 
> the following Gnulib modules have unnecessary lines like that. These 
> unnecessary lines don't break builds of course.

Thanks, I removed them now.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.