GNU bug report logs - #69864
30.0.50; Problem with equal hash tables

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 69864 in the body.
You can then email your comments to 69864 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: Gerd Möllmann <gerd.moellmann <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Subject: 30.0.50; Problem with equal hash tables
Date: Sun, 17 Mar 2024 18:59:51 +0100

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

This is in master, 562d9c9db56172c754a2556a996245145ae223f5

I suspect we have a problem with equal hash-tables in master. Apply the
attached patch, configure with checking enabled, and build it.

[0001-check_table.patch (text/x-patch, attachment)]

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

This adds a check that all collision lists of hash-tables are ok. I
originally added something similar in my local Emacs because I'm
changing the hash-table implementation, for reasons that have to do with
changing the GC.

The compilation will fail with 

  Loading /Users/gerd/emacs/savannah/master/lisp/emacs-lisp/cl-generic.el (source)...

  fns.c:4527: Emacs fatal error: assertion failed: hash == HASH_HASH (h, i)
  Fatal error 6: Aborted

I don't think I have an error in the checking code, but who knows.
If there's no error in the checks, then we might have a problem with
sxhash, I suspect.

LLDB session:

(lldb) r --batch  -l loadup --temacs=pbootstrap -dest /Users/gerd/emacs/savannah/master/nextstep/Emacs.app/Contents/MacOS/ --eln-dest /Users/gerd/emacs/savannah/master/nextstep/Emacs.app/Contents/Frameworks/
Process 90778 launched: '/Users/gerd/emacs/savannah/master/src/temacs' (x86_64)
...
Loading /Users/gerd/emacs/savannah/master/lisp/emacs-lisp/cl-generic.el (source)...

fns.c:4527: Emacs fatal error: assertion failed: hash == HASH_HASH (h, i)
Process 90778 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = signal SIGABRT
    frame #0: 0x00007ff80a71414a libsystem_kernel.dylib`__pthread_kill + 10
libsystem_kernel.dylib`__pthread_kill:
->  0x7ff80a71414a <+10>: jae    0x7ff80a714154            ; <+20>
    0x7ff80a71414c <+12>: movq   %rax, %rdi
    0x7ff80a71414f <+15>: jmp    0x7ff80a70db20            ; cerror_nocancel
    0x7ff80a714154 <+20>: retq   
(lldb) up 10
frame #10: 0x00000001002cc88c temacs`hash_lookup_with_hash(h=0x00007fb1f89211a0, key=(struct Lisp_Cons *) $4 = 0x00007fb1fbab76c0, hash=1339923535) at fns.c:4813:3
(lldb) do
frame #9: 0x00000001002d39f1 temacs`check_table(h=0x00007fb1f89211a0) at fns.c:4527:4
(lldb) p hash 
(hash_hash_t) 664518371
(lldb) p h->hash[i]
(hash_hash_t) 26984166
(lldb) xdebug_print h->key_and_value[2*i]
(#s(cl--generic cl-generic-generalizers ((0 #s(cl--generic-generalizer cl--generic-t-generalizer 0 (closure (cl-struct-cl--generic-generalizer-tags t) (_name &rest _) nil) (closure (cl-struct-cl--generic-generalizer-tags t) (_tag &rest _) '(t))))) (#s(cl--generic-method (t) (:extra "head") curried (closure (cl-struct-cl--generic-tags cl-struct-cl--generic-method-tags cl-struct-cl--generic-generalizer-tags t) (cl--nm) (let ((cl--nmp (if (cl--generic-isnot-nnm-p cl--nm) #'always #'ignore))) #'(lambda (&rest cl--args) "Support for (head VAL) specializers.
These match if the argument is a cons cell whose car is `eql' to VAL.

(fn SPECIALIZER)" (let ((cl--cnm #'(lambda (&rest args) (apply cl--nm (or args cl--args))))) (apply #'(lambda (cl--cnm specializer) (progn (if (not (eq (car-safe specializer) 'head)) (funcall cl--cnm) (let* ((v (car (cdr specializer))) (v cl--generic-head-used)) (or (gethash v v) (let* ((val specializer)) (progn (puthash v val v) val)))) (list cl--generic-head-generalizer)))) cl--cnm cl--args)))))) #s(cl--generic-method (t) nil nil (closure (cl-struct-cl--generic-tags cl-struct-cl--generic-method-tags cl-struct-cl--generic-generalizer-tags t) (specializer) "Support for the catch-all t specializer which always matches." (progn (if (eq specializer t) (list cl--generic-t-generalizer) (error "Unknown specializer %S" specializer)))))) nil) #s(cl--generic-method (t) nil nil (closure (cl-struct-cl--generic-tags cl-struct-cl--generic-method-tags cl-struct-cl--generic-generalizer-tags t) (specializer) "Support for the catch-all t specializer which always matches." (progn (if (eq specializer t) (list cl--generic-t-generalizer) (error "Unknown specializer %S" specializer))))))
(lldb) p h->test
(const hash_table_test *) 0x000000010049e7e8
(lldb) p h->frozen_test 
(hash_table_std_test_t) Test_eq | Test_equal
(lldb) p *h
(Lisp_Hash_Table) {
  header = (size = 4611686018662301696)
  index = 0x0000600001cf41a0
  hash = 0x0000600001cf4180
  key_and_value = 0x00006000038f4060 (struct Lisp_Symbol *) $27 = 0x000060010439bcb0
  test = 0x000000010049e7e8
  next = 0x0000600001cf4160
  count = 5
  next_free = 5
  table_size = 6
  index_bits = '\x03'
  weakness = Weak_Value
  frozen_test = Test_eq | Test_equal
  purecopy = false
  mutable = true
  next_weak = NULL
}
(lldb) xbacktrace 
(unsigned char *) data = 0x0000000100481d88 "gethash"
(unsigned char *) data = 0x00000001004812d4 "or"
(unsigned char *) data = 0x00000001004813af "let*"
(unsigned char *) data = 0x00000001004813ab "let"
(unsigned char *) data = 0x00000001004812db "if"
(unsigned char *) data = 0x00007fb1f8a41978 "cl--generic-build-combined-method"
(unsigned char *) data = 0x00000001004812db "if"
(unsigned char *) data = 0x00000001004813af "let*"
(unsigned char *) data = 0x00007fb1f8a41950 "cl--generic-make-next-function"
(unsigned char *) data = 0x00007fb1f8a40d58 "cl--generic-make-function"
(unsigned char *) data = 0x00000001004813ab "let"
(unsigned char *) data = 0x00000001004812e3 "progn"
(unsigned char *) data = 0x00000001004813af "let*"
(unsigned char *) data = 0x00000001004813ab "let"
(unsigned char *) data = 0x00000001004813af "let*"
(unsigned char *) data = 0x00000001004812e3 "progn"
(unsigned char *) data = 0x00000001004813af "let*"
(unsigned char *) data = 0x00007fb1f8a41478 "cl-generic-define-method"
(unsigned char *) data = 0x0000000100487f58 "eval-buffer"
(unsigned char *) data = 0x00000001004812db "if"
(unsigned char *) data = 0x00000001004813ab "let"
(unsigned char *) data = 0x00000001004813ab "let"
(unsigned char *) data = 0x00000001004813ef "unwind-protect"
(unsigned char *) data = 0x00000001004813ab "let"
(unsigned char *) data = 0x00000001004812db "if"
(unsigned char *) data = 0x00007fb1f883bb28 "load-with-code-conversion"
(unsigned char *) data = 0x0000000100486664 "load"
(unsigned char *) data = 0x0000000100486664 "load"

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

From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
To: 69864 <at> debbugs.gnu.org
Cc: Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#69864: 30.0.50; Problem with equal hash tables
Date: Sun, 17 Mar 2024 19:56:24 +0100

Gerd Möllmann <gerd.moellmann <at> gmail.com> writes:

> (unsigned char *) data = 0x00007fb1f8a41978 "cl--generic-build-combined-method"

Or, and maybe more plausible, someone modifies the hash-table keys used
in the function above...

Stefan is in Cc.

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

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Gerd Möllmann <gerd.moellmann <at> gmail.com>
Cc: 69864 <at> debbugs.gnu.org
Subject: Re: bug#69864: 30.0.50; Problem with equal hash tables
Date: Sun, 17 Mar 2024 16:38:19 -0400

Gerd Möllmann [2024-03-17 19:56:24] wrote:
> Gerd Möllmann <gerd.moellmann <at> gmail.com> writes:
>> (unsigned char *) data = 0x00007fb1f8a41978 "cl--generic-build-combined-method"
> Or, and maybe more plausible, someone modifies the hash-table keys used
> in the function above...

Lessee...

    (defun cl--generic-build-combined-method (generic methods)
      (let ((f
             (with-memoization
                 ;; FIXME: Since the fields of `generic' are modified, this
                 ;; hash-table won't work right, because the hashes will change!
                 ;; It's not terribly serious, but reduces the effectiveness of
                 ;; the table.
                 (gethash (cons generic methods)
                          cl--generic-combined-method-memoization)
    [...]

I suspect The Right Way would involve flushing the elements of the cache
when the generic is modified, or otherwise changing the hash-table index
so it doesn't include `generic` at all, or only the part that does
matter (as the code points out later on, currently this arg is not used
for much).

FWIW, I've never really measured the effectiveness of this cache.
It'd be worthwhile to do it at some point, because there's a good chance
its hit rater is very low (e.g. because its `:weakness` makes it lose
its info before we need it).


        Stefan

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

From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 69864 <at> debbugs.gnu.org
Subject: Re: bug#69864: 30.0.50; Problem with equal hash tables
Date: Mon, 18 Mar 2024 08:45:12 +0100

Stefan Monnier <monnier <at> iro.umontreal.ca> writes:

> Gerd Möllmann [2024-03-17 19:56:24] wrote:
>> Gerd Möllmann <gerd.moellmann <at> gmail.com> writes:
>>> (unsigned char *) data = 0x00007fb1f8a41978 "cl--generic-build-combined-method"
>> Or, and maybe more plausible, someone modifies the hash-table keys used
>> in the function above...
>
> Lessee...
>
>     (defun cl--generic-build-combined-method (generic methods)
>       (let ((f
>              (with-memoization
>                  ;; FIXME: Since the fields of `generic' are modified, this
>                  ;; hash-table won't work right, because the hashes will change!
>                  ;; It's not terribly serious, but reduces the effectiveness of
>                  ;; the table.

Oh, I didn't read that comment, of course :-). Thanks!

I guess I'll try to ignore that hash-table somehow in my checks. It seems
it's the only one in Emacs making problems.

And I think I'll close this report if it's a known problem anyway.

Previous Next

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