GNU bug report logs - #69709
`sort` interface improvement and universal ordering predicate

Previous Next

Full log

View this message in rfc822 format

From: Eli Zaretskii <eliz <at> gnu.org>
To: Aris Spathis <agspathis <at> gmail.com>, Mattias Engdegård <mattiase <at> acm.org>
Cc: 69709 <at> debbugs.gnu.org, mattias.engdegard <at> gmail.com
Subject: bug#69709: `sort` interface improvement and universal ordering predicate
Date: Sun, 14 Apr 2024 19:26:05 +0300

> Cc: 69709 <at> debbugs.gnu.org
> From: Aris Spathis <agspathis <at> gmail.com>
> Date: Sun, 14 Apr 2024 17:03:11 +0300
> 
> Thank you for your excellent work on `sort` and related functionality!
> 
> Unfortunately, the new `sort` implementation occasionally crashes with a
> segfault. The following code reproduces that in current master:
> 
> (dotimes (i 500)
>   (sort (make-list 128 42)
>         :key (lambda (n) (make-list i n))))
> 
> It happens for inputs of length >= `MERGESTATE_TEMP_SIZE / 2` (= 128
> currently) along with a non-NIL `:key` function. In such cases, a
> `Lisp_Object` array is explicitly heap-allocated to store the keys, which is
> never marked against GC. This would not be a problem if not for the fact that
> the `:key` function call may trigger GC.
> 
> I'm attaching a patch with a proposed solution, consisting of three changes:
> 
> 1. Allocate with `xzalloc` to have the new array initialized to `Qnil`. This
>    ensures its objects can be marked properly.
> 
> 2. Mark `ms->allocated_keys` in `merge_markmem`. We don't need to check that
>    `ms->allocated_keys != NULL`, as `merge_register_cleanup` is only called
>    under this exact condition.
> 
> 3. Move the computation of keys (which may trigger a GC) after `merge_init`,
>    which registers `merge_markmem`.
> 
> I hope this is useful.

Thanks, I took the liberty of CC'ing Mattias using his "usual"
address, in the hope that it will help bring this to his attention
sooner.

Previous Next

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