Subject: Re: bug#36447: 27.0.50; New "Unknown keyword" errors

From: Pip Cet <[email-masked]>
Date: Wed, 3 Jul 2019 11:57:52 +0000

On Tue, Jul 2, 2019 at 10:50 PM Pip Cet <[email-masked]> wrote:
> > The compiler translates repeated `eq' in a cond like that into a hash
> > and jump.  See byte-compile-cond-use-jump-table.
>
> I think I found the problem. It's a bit tricky.

I'm attaching a patch which modifies standard Emacs in what should be
harmless ways, but demonstrates the bug.

As far as I can tell, this is a serious issue that will pop up
seemingly at random. We really should fix it.

However, I thought hash_table_rehash was called more often than it
actually is, so the fix should be simple: just copy-sequence a hash
table's ->next, ->hash, and ->index vectors before rehashing.
(->key_and_value isn't actually modified, so it's safe to share
between (read-only) hash tables.

What's happening is this:

Purecopied hash tables share structure, particularly the ->next
vector, with similar but different purecopied hash tables. Some
purecopied hash tables dumped with pdumper are rehashed upon first
access after loading the dump (in the example, this is the tables
which map 'dummy-symbol to t), while others are not (the tables with
just fixnums as keys). If a hash table is rehashed, it's ->next vector
will change to reflect the changed hash (of 'dummy-symbol); however,
the non-rehashed table that shares the ->next vector will be confused:
its key_and_value array will stay the same, and valid, but the ->next
vector will no longer match it. In practice, this means (gethash
valid-key hash-table) will return nil even though the key is valid.

While the attached patch appears to work, I would prefer simply
dumping hash tables with nil values for ->next, ->hash, and ->index,
and rebuilding the entire hash table upon first access. This would
also allow us to switch to secure randomized hashes should the need
arise.
From 8fe464dbb030a722ca173c442906482ef210f46e Mon Sep 17 00:00:00 2001
From: Pip Cet <[email-masked]>
Date: Wed, 3 Jul 2019 11:27:50 +0000
Subject: [PATCH 1/2] Test bug#36447

---
 lisp/custom.el | 10 ++++++++++
 src/puresize.h |  2 +-
 test-custom.el | 12 ++++++++++++
 3 files changed, 23 insertions(+), 1 deletion(-)
 create mode 100644 test-custom.el

diff --git a/lisp/custom.el b/lisp/custom.el
index 736460fec7..c49321b829 100644
--- a/lisp/custom.el
+++ b/lisp/custom.el
@@ -35,6 +35,16 @@
 
 (require 'widget)
 
+(defvar hash-tables (make-vector 256 nil))
+
+(dotimes (i 256)
+  (let ((ht (make-hash-table :purecopy t :size 2 :test 'eq)))
+    (when (= (% i 3) 0)
+      (puthash 'dummy-symbol t ht))
+    (dotimes (j 16)
+      (puthash (logand i (lsh 1 j)) t ht))
+    (aset hash-tables i (purecopy ht))))
+
 (defvar custom-define-hook nil
   ;; Customize information for this option is in `cus-edit.el'.
   "Hook called after defining each customize option.")
diff --git a/src/puresize.h b/src/puresize.h
index f5fad8b42b..d29e3e80df 100644
--- a/src/puresize.h
+++ b/src/puresize.h
@@ -47,7 +47,7 @@ #define SITELOAD_PURESIZE_EXTRA 0
 #endif
 
 #ifndef BASE_PURESIZE
-#define BASE_PURESIZE (2000000 + SYSTEM_PURESIZE_EXTRA + SITELOAD_PURESIZE_EXTRA)
+#define BASE_PURESIZE (80000000 + SYSTEM_PURESIZE_EXTRA + SITELOAD_PURESIZE_EXTRA)
 #endif
 
 /* Increase BASE_PURESIZE by a ratio depending on the machine's word size.  */
diff --git a/test-custom.el b/test-custom.el
new file mode 100644
index 0000000000..b871d30cfa
--- /dev/null
+++ b/test-custom.el
@@ -0,0 +1,12 @@
+(dotimes (i 256)
+  (let ((ht (aref hash-tables i)))
+    (dotimes (j 16)
+      (unless (eq (/= 0 (logand (lsh 1 j) i))
+                  (gethash (lsh 1 j) ht))
+        (error "hash table corruption at table %S, bit %S" i j)))))
+
+(aref hash-tables 17)
+;; #s(hash-table size 3 test eq rehash-size 1.5 rehash-threshold 0.8125 purecopy t data (1 t 0 t 16 t))
+
+(gethash 1 (aref hash-tables 17))
+;; nil
-- 
2.20.1

From 70419f630f60919c8645a10aeef8d299f5098ff5 Mon Sep 17 00:00:00 2001
From: Pip Cet <[email-masked]>
Date: Wed, 3 Jul 2019 11:48:22 +0000
Subject: [PATCH 2/2] Don't alter shared structure in dumped purecopied hash
 tables.

* src/fns.c (hash_table_rehash): Make sure we're operating on
fresh copies of ->next, ->index, ->hash.
---
 src/fns.c | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/src/fns.c b/src/fns.c
index 2fc000a7f4..44d2de523a 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -4223,6 +4223,12 @@ hash_table_rehash (struct Lisp_Hash_Table *h)
 {
   ptrdiff_t size = HASH_TABLE_SIZE (h);
 
+  /* These structures may have been purecopied and shared
+     (bug#36447).  */
+  h->next = Fcopy_sequence (h->next);
+  h->index = Fcopy_sequence (h->index);
+  h->hash = Fcopy_sequence (h->hash);
+
   /* Recompute the actual hash codes for each entry in the table.
      Order is still invalid.  */
   for (ptrdiff_t i = 0; i < size; ++i)
-- 
2.20.1