Linus Torvalds
65a9b4df5a
assoc_array: don't chain a new shortcut onto an existing one
...
When a full node's leaves and the new key all share the node's segment,
assoc_array_insert_into_terminal_node() replaces the node with a
shortcut to a pair of new nodes. If the node is itself the target of a
shortcut, the new shortcut is installed as that shortcut's next node,
and a shortcut leading to a shortcut is something nothing expects:
assoc_array_walk() indexes the second one as a node, and
assoc_array_apply_edit() hits the BUG_ON() in the loop that adjusts
nr_leaves_on_branch, on that same insertion.
Deletion gets a node there. When the subtree below a shortcut shrinks
enough, assoc_array_delete() collapses it into one node below the
shortcut, and the leaves it collects can all share that node's segment.
The next key that shares it too takes this path. Eighteen insertions
and a deletion are enough: sixteen keys that agree on bits 0-11, one
that leaves them at bit 8 and is deleted again, and one more that agrees
with the sixteen.
Have the new shortcut replace the one in front of the node as well.
assoc_array_insert_shortcut() gives it that shortcut's back pointer and
parent slot, so the caller installs it where that one was, and excises
the old shortcut along with the node, which takes a second entry in
excised_meta[]. The new shortcut's index key comes from the new key up
to the new skip level, so it covers what the old one did.
Found by a userspace test doing random insertions and deletions on keys
that share long prefixes; a targeted case builds a shortcut, deletes
down to the collapse and inserts one more key.
Fixes: 3cb989501c ("Add a generic associative array implementation.")
Reported-by: Ollrogge <nils-ollrogge@outlook.de >
Assisted-by: LLM
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org >
2026-10-11 12:42:26 -07:00
..
2026-07-03 07:38:16 +02:00
2026-07-17 12:46:24 +02:00
2026-07-23 10:24:12 -07:00
2026-08-07 14:18:13 -03:00
2026-10-01 17:05:03 +02:00
2026-07-03 07:38:16 +02:00
2026-08-26 19:57:28 +02:00
2026-08-20 16:51:33 -07:00
2026-07-03 07:38:14 +02:00
2026-08-31 16:25:38 +02:00
2026-08-24 12:21:15 -07:00
2026-05-21 13:04:42 +02:00
2026-08-25 14:03:31 -07:00
2026-08-17 19:04:16 -07:00
2026-08-20 08:16:04 -07:00
2026-05-19 10:45:38 +02:00
2026-07-30 11:05:07 +02:00
2026-07-17 16:14:13 +02:00
2026-08-23 13:28:57 -07:00
2026-08-26 14:21:30 -07:00
2026-08-09 14:48:47 -07:00
2026-08-17 17:02:10 +02:00
2026-08-20 10:23:53 +02:00
2026-08-03 21:53:54 +03:00
2026-08-10 09:54:35 -04:00
2026-08-27 10:45:08 -07:00
2026-07-17 15:50:48 +02:00
2026-08-27 13:53:43 -07:00
2026-07-27 16:03:40 -07:00
2026-09-04 20:32:21 +02:00
2026-05-05 14:48:12 +02:00
2026-08-12 13:56:51 -07:00
2026-08-06 11:53:47 -07:00
2026-09-07 18:48:52 +02:00
2026-05-08 01:30:16 +02:00
2026-05-08 01:30:16 +02:00
2026-08-21 13:59:05 +02:00
2026-08-05 17:59:29 -07:00
2026-09-01 19:19:26 -06:00
2026-05-05 14:48:12 +02:00
2026-08-27 10:45:08 -07:00
2026-07-27 20:32:38 +02:00
2026-08-26 10:05:45 +02:00
2026-05-28 21:24:54 -07:00
2026-07-03 07:38:16 +02:00
2026-05-20 17:17:04 +01:00
2026-10-07 02:03:46 +02:00
2026-09-23 12:22:40 +02:00
2026-08-24 12:16:16 -07:00
2026-08-10 18:00:47 +01:00
2026-07-17 12:46:24 +02:00
2026-08-21 11:48:54 -07:00
2026-07-03 07:38:16 +02:00
2026-07-03 07:38:16 +02:00
2026-09-08 11:00:48 +02:00
2026-07-09 15:30:19 +02:00
2026-07-21 23:04:13 +02:00
2026-08-18 08:47:09 -07:00
2026-04-28 19:16:02 -07:00
2026-05-01 21:36:14 +02:00
2026-07-30 19:40:44 -07:00
2026-08-24 10:16:35 -07:00
2026-07-15 12:13:30 +02:00
2026-08-02 09:21:06 +00:00
2026-06-17 11:21:40 -07:00
2026-10-11 12:42:26 -07:00
2026-08-19 12:31:50 -07:00
2026-07-29 17:54:58 -07:00
2026-05-26 17:15:30 -04:00
2026-05-26 17:15:30 -04:00
2026-07-03 07:38:16 +02:00
2026-06-04 10:16:51 +02:00
2026-08-04 19:18:48 -07:00
2026-08-03 23:36:18 +02:00
2026-08-03 19:15:44 +02:00
2026-08-04 07:22:27 -06:00
2026-08-15 17:09:32 -06:00
2026-05-20 11:18:27 -04:00
2026-05-28 11:36:53 -04:00
2026-07-22 15:38:38 -04:00
2026-05-28 11:39:16 -04:00
2026-07-22 15:38:36 -04:00
2026-08-04 06:57:05 -06:00
2026-08-20 13:55:16 -07:00
2026-08-15 17:15:08 -06:00
2026-07-20 10:39:26 -07:00
2026-05-28 09:35:38 -06:00
2026-08-20 13:55:16 -07:00
2026-07-02 21:15:45 +09:00
2026-05-23 01:50:33 -07:00
2026-08-15 23:36:18 +02:00
2026-06-30 16:31:56 +02:00
2026-06-07 10:03:01 -07:00
2026-09-22 19:34:04 +00:00
2026-05-31 09:16:55 -07:00
2026-09-29 05:54:16 +00:00
2026-06-07 10:03:01 -07:00
2026-09-10 16:55:47 -07:00
2026-07-27 16:25:34 +02:00
2026-08-06 06:47:33 -06:00
2026-05-18 21:33:15 +02:00
2026-05-26 12:28:32 -07:00
2026-08-21 09:09:54 +02:00
2026-04-27 15:52:51 -06:00
2026-06-06 15:08:36 -07:00
2026-08-06 23:38:03 +02:00
2026-07-26 03:11:00 -04:00
2026-08-31 06:19:38 -10:00
2026-08-21 08:41:00 -07:00
2026-06-05 14:46:51 +02:00
2026-08-20 16:51:47 -07:00
2026-07-28 11:25:30 -04:00
2026-06-15 13:51:27 +05:30
2026-04-27 09:56:38 -07:00
2026-08-24 18:43:12 -07:00
2026-08-06 18:57:24 -07:00
2026-05-28 06:51:30 -07:00
2026-06-15 14:21:14 +05:30
2026-06-15 14:21:14 +05:30
2026-06-15 05:01:15 +05:30
2026-05-28 12:20:19 +02:00
2026-10-02 10:26:42 +02:00
2026-05-22 11:47:33 +02:00
2026-07-15 07:15:26 +02:00
2026-05-26 11:02:01 +02:00
2026-06-22 12:20:21 -07:00
2026-09-29 12:23:20 +02:00
2026-07-15 15:06:34 +02:00
2026-06-04 10:55:27 +02:00
2026-07-22 15:38:37 -04:00
2026-08-22 16:40:23 -07:00
2026-06-30 18:49:06 +03:00
2026-06-30 18:49:06 +03:00
2026-07-07 15:10:48 -04:00
2026-05-28 17:45:46 -07:00
2026-08-06 18:57:22 -07:00
2026-06-05 00:34:55 -04:00
2026-07-15 15:04:55 +02:00
2026-08-27 12:00:16 -04:00
2026-06-29 00:59:24 +02:00
2026-07-03 07:38:16 +02:00
2026-08-05 17:41:38 -07:00
2026-05-18 11:16:29 +02:00
2026-07-27 23:09:28 +02:00
2026-08-24 13:57:59 +02:00
2026-07-31 08:40:59 +02:00
2026-08-31 11:00:46 +02:00
2026-08-31 11:00:46 +02:00
2026-07-02 09:27:51 +02:00
2026-09-15 10:02:53 +02:00
2026-07-31 08:40:58 +02:00
2026-07-31 08:40:58 +02:00
2026-07-17 18:00:34 +05:30
2026-08-10 10:04:07 +02:00
2026-07-03 07:38:16 +02:00
2026-06-13 13:24:34 -07:00
2026-06-29 18:18:51 -07:00
2026-08-20 14:49:39 +03:00
2026-07-03 07:38:16 +02:00
2026-09-07 11:17:54 +02:00
2026-06-04 14:49:27 -07:00
2026-08-20 13:04:44 -07:00
2026-09-18 17:19:15 -07:00
2026-05-15 17:41:05 +02:00
2026-08-24 18:43:09 -07:00
2026-05-11 11:11:48 +02:00
2026-05-11 11:11:48 +02:00
2026-06-22 19:52:36 +00:00
2026-06-09 16:00:11 +02:00
2026-05-21 15:33:47 +02:00
2026-05-11 16:50:27 +02:00
2026-06-15 03:59:45 +05:30
2026-08-20 17:52:31 +02:00
2026-05-28 11:36:59 -04:00
2026-07-03 07:38:16 +02:00
2026-05-06 16:37:48 +02:00
2026-08-02 19:25:47 -07:00
2026-08-21 09:49:54 -07:00
2026-06-18 16:39:31 -07:00
2026-05-11 19:04:46 +09:00
2026-06-29 10:44:05 +02:00
2026-10-04 12:36:13 +02:00
2026-07-20 10:39:26 -07:00
2026-06-15 02:50:44 +05:30
2026-05-15 19:24:33 +02:00
2026-06-05 13:36:22 +02:00
2026-09-01 16:38:19 -04:00
2026-06-03 11:38:51 +02:00
2026-08-16 00:16:32 +02:00
2026-07-30 16:16:01 +02:00
2026-07-30 19:40:44 -07:00
2026-08-06 18:57:11 -07:00
2026-07-07 10:42:28 -04:00
2026-07-03 13:01:52 +02:00
2026-07-24 20:12:40 +02:00
2026-05-04 09:59:19 +02:00
2026-08-06 16:58:54 +05:30
2026-08-10 10:50:19 +02:00
2026-05-21 11:45:52 +02:00
2026-07-20 12:17:57 -07:00
2026-05-12 18:03:37 +02:00
2026-06-29 23:24:46 +01:00
2026-08-19 09:27:26 +02:00
2026-05-28 21:05:08 -07:00
2026-05-13 17:40:02 -07:00
2026-05-29 13:54:43 +08:00
2026-08-04 19:18:54 -07:00
2026-05-28 17:19:28 +02:00
2026-08-11 18:11:20 +02:00
2026-09-29 23:42:11 +02:00
2026-07-07 23:43:45 +02:00
2026-08-06 18:57:16 -07:00
2026-07-28 21:11:48 -07:00
2026-05-21 19:06:11 -07:00
2026-08-04 19:19:06 -07:00
2026-08-10 08:59:43 -07:00
2026-07-31 16:32:38 +02:00
2026-08-24 00:35:41 +00:00
2026-07-29 20:51:16 +02:00
2026-06-17 00:15:09 +02:00
2026-07-03 07:38:16 +02:00
2026-07-27 16:03:40 -07:00
2026-09-04 09:54:42 +02:00
2026-06-08 08:59:03 +02:00
2026-07-21 19:18:52 +02:00
2026-07-07 10:16:31 +02:00
2026-06-05 17:46:17 -07:00
2026-08-07 17:29:15 -07:00
2026-09-19 15:47:15 -07:00
2026-08-31 17:22:03 -07:00
2026-07-08 14:41:01 +02:00
2026-06-29 10:44:05 +02:00
2026-05-28 21:24:43 -07:00
2026-08-05 23:01:44 -07:00
2026-05-14 10:44:16 +02:00
2026-05-07 16:06:28 +03:00
2026-06-15 02:13:01 +03:00
2026-07-03 07:38:16 +02:00
2026-06-06 19:51:14 -05:00
2026-08-30 20:25:21 +02:00
2026-05-26 16:21:11 +02:00
2026-08-25 07:59:44 -07:00
2026-08-20 13:55:16 -07:00
2026-04-26 23:38:35 +02:00
2026-07-26 13:16:21 -03:00
2026-06-23 12:08:51 -05:00
2026-07-03 07:38:16 +02:00
2026-07-12 12:38:01 +02:00
2026-05-26 16:21:13 +02:00
2026-07-07 21:36:18 +02:00
2026-09-04 08:40:07 +02:00
2026-07-03 07:38:16 +02:00
2026-07-22 23:47:23 -04:00
2026-07-31 10:32:24 +02:00
2026-05-28 21:24:51 -07:00
2026-04-30 15:45:32 +02:00
2026-06-15 16:33:40 +02:00
2026-08-10 10:50:19 +02:00
2026-06-06 15:21:40 +02:00
2026-08-04 09:25:55 +03:00
2026-07-01 13:02:31 +03:00
2026-06-03 21:15:46 +03:00
2026-08-04 09:22:36 +03:00
2026-07-11 20:38:01 +02:00
2026-09-03 09:04:25 +09:00
2026-06-30 00:15:52 +01:00
2026-09-26 00:49:49 -04:00
2026-08-17 10:17:13 +02:00
2026-08-04 19:18:36 -07:00
2026-06-17 11:28:52 +01:00
2026-07-23 14:08:22 +01:00
2026-09-21 13:08:58 +02:00
2026-08-19 06:38:45 -04:00
2026-06-05 11:44:10 +01:00
2026-06-08 18:21:24 -07:00
2026-08-23 08:07:11 -07:00
2026-07-25 15:26:30 +03:00
2026-05-26 17:26:57 -07:00
2026-08-05 11:20:13 -07:00
2026-08-24 18:43:28 -07:00
2026-08-24 18:43:28 -07:00
2026-07-31 10:09:12 +02:00
2026-05-01 11:29:33 -04:00
2026-08-04 12:35:02 -04:00
2026-05-18 13:35:32 -05:00
2026-08-24 18:43:32 -07:00
2026-06-30 00:15:52 +01:00
2026-07-03 07:38:16 +02:00
2026-07-17 15:43:32 +02:00
2026-07-03 07:38:16 +02:00
2026-08-04 09:29:03 +03:00
2026-08-27 09:17:06 -07:00
2026-08-06 18:57:01 -07:00
2026-08-06 18:56:59 -07:00
2026-08-06 18:56:58 -07:00
2026-09-25 17:30:39 +02:00
2026-07-30 07:19:51 +02:00
2026-08-07 16:13:17 +02:00
2026-07-28 21:11:50 -07:00
2026-07-28 21:11:50 -07:00
2026-08-06 18:57:20 -07:00
2026-09-22 10:50:35 +02:00
2026-08-24 18:42:50 -07:00
2026-09-09 08:38:56 +02:00
2026-06-02 15:22:16 -07:00
2026-08-24 18:43:06 -07:00
2026-07-16 22:40:17 -04:00
2026-08-06 13:29:03 +02:00
2026-07-31 14:19:04 +02:00
2026-09-26 15:47:41 +02:00
2026-06-11 15:17:30 -07:00
2026-05-11 16:22:15 +02:00
2026-07-23 15:42:48 +02:00
2026-07-30 15:42:58 -07:00
2026-08-20 08:16:04 -07:00
2026-06-12 16:43:10 -07:00
2026-09-30 09:35:20 +02:00
2026-09-29 17:49:35 -07:00
2026-07-02 12:17:14 +02:00
2026-09-30 14:22:44 -03:00
2026-07-30 12:14:39 +02:00
2026-08-26 15:09:21 -07:00
2026-05-11 16:50:29 +02:00
2026-08-27 09:17:06 -07:00
2026-06-08 12:06:41 -04:00
2026-08-20 15:18:20 -07:00
2026-08-23 08:07:11 -07:00
2026-07-22 15:38:37 -04:00
2026-10-01 14:20:07 +02:00
2026-06-26 22:18:34 -04:00
2026-04-27 15:47:21 -06:00
2026-09-03 14:15:11 -07:00
2026-07-06 11:13:43 -07:00
2026-07-31 11:00:13 +02:00
2026-07-21 10:53:24 +02:00
2026-08-07 18:27:18 +02:00
2026-08-07 18:27:18 +02:00
2026-08-11 18:54:17 -05:00
2026-07-03 07:38:16 +02:00
2026-08-11 16:54:37 -05:00
2026-07-03 07:38:16 +02:00
2026-07-28 21:12:04 -07:00
2026-08-24 18:43:03 -07:00
2026-07-28 21:11:50 -07:00
2026-06-04 14:45:07 -07:00
2026-07-09 15:48:56 -07:00
2026-07-28 21:11:47 -07:00
2026-06-02 15:22:19 -07:00
2026-08-24 18:42:50 -07:00
2026-05-22 12:19:02 +02:00
2026-08-23 12:44:10 -07:00
2026-05-28 09:34:41 +02:00
2026-07-20 14:59:56 +02:00
2026-04-30 21:48:22 +05:30
2026-07-03 07:38:16 +02:00
2026-08-23 12:44:10 -07:00
2026-08-23 12:44:10 -07:00
2026-08-24 18:43:24 -07:00
2026-07-28 21:11:55 -07:00
2026-06-11 13:41:25 +02:00
2026-06-16 08:44:43 +05:30
2026-10-01 14:02:06 +02:00
2026-07-28 21:11:46 -07:00
2026-08-04 19:18:36 -07:00
2026-06-09 10:13:04 -07:00
2026-07-31 18:22:48 -07:00
2026-08-13 18:21:31 -07:00
2026-06-10 11:08:23 +02:00
2026-08-12 11:36:41 +02:00
2026-08-10 01:20:05 +02:00
2026-05-11 12:46:42 +02:00
2026-07-03 07:38:16 +02:00
2026-07-20 16:05:42 +02:00
2026-08-11 18:11:19 +02:00
2026-08-07 02:43:11 +02:00
2026-08-03 21:10:10 -07:00
2026-08-30 20:25:21 +02:00
2026-05-11 23:13:01 +02:00
2026-07-23 23:08:04 +02:00
2026-07-15 05:00:53 -10:00
2026-07-05 13:25:36 +08:00
2026-06-04 11:04:18 +02:00
2026-08-07 17:29:16 -07:00
2026-07-12 12:38:02 +02:00
2026-07-28 21:12:01 -07:00
2026-07-12 12:38:00 +02:00
2026-09-10 10:22:52 +02:00
2026-08-05 11:20:12 -07:00
2026-08-05 11:20:12 -07:00
2026-07-24 16:54:07 -07:00
2026-08-14 15:43:51 -07:00
2026-07-23 10:46:09 -07:00
2026-08-24 10:58:57 -07:00
2026-07-23 10:46:09 -07:00
2026-07-23 10:46:09 -07:00
2026-07-23 19:21:13 +01:00
2026-08-04 17:32:02 -05:00
2026-07-23 13:10:52 -07:00
2026-07-28 15:59:03 +02:00
2026-06-15 03:05:50 +05:30
2026-07-05 13:19:51 +08:00
2026-09-13 13:06:43 -04:00
2026-07-03 07:38:16 +02:00
2026-08-24 18:42:54 -07:00
2026-08-31 09:54:38 +02:00
2026-07-03 07:38:16 +02:00
2026-08-04 17:32:02 -05:00
2026-08-10 09:37:54 +02:00
2026-05-06 17:40:15 +02:00
2026-05-05 16:02:57 +02:00
2026-06-23 00:13:21 +02:00
2026-05-19 13:49:01 +02:00
2026-09-29 17:49:35 -07:00
2026-07-13 13:15:02 +02:00
2026-09-22 10:50:43 +02:00
2026-05-05 15:45:35 +01:00
2026-05-12 15:29:12 +01:00
2026-07-12 12:38:02 +02:00
2026-05-01 11:29:33 -04:00
2026-07-31 10:09:14 +02:00
2026-05-28 12:23:22 +02:00
2026-08-03 16:51:57 +02:00
2026-08-03 16:51:57 +02:00
2026-06-29 12:06:07 +02:00
2026-05-11 16:56:08 +02:00
2026-07-03 07:38:16 +02:00
2026-08-24 18:43:14 -07:00
2026-09-16 11:48:10 +02:00
2026-09-29 17:49:35 -07:00
2026-07-15 11:10:14 +02:00
2026-08-24 15:01:27 +02:00
2026-07-03 07:38:16 +02:00
2026-05-01 16:24:25 -05:00
2026-07-16 09:24:55 +02:00
2026-08-15 23:36:18 +02:00
2026-05-11 12:25:31 +02:00
2026-08-10 10:50:18 +02:00
2026-08-10 10:50:18 +02:00
2026-08-10 10:50:18 +02:00
2026-08-24 12:58:54 +02:00
2026-05-28 18:40:46 -07:00
2026-08-23 18:00:22 -07:00
2026-07-15 15:34:25 -07:00
2026-07-15 15:34:25 -07:00
2026-08-05 11:20:13 -07:00
2026-08-12 11:36:39 +02:00
2026-07-31 10:32:24 +02:00
2026-05-12 21:48:36 -07:00
2026-07-31 12:35:26 +02:00
2026-06-18 16:39:31 -07:00
2026-08-24 18:43:20 -07:00
2026-08-24 18:43:20 -07:00
2026-08-24 18:43:26 -07:00
2026-08-24 11:35:46 -07:00
2026-05-05 12:06:37 -05:00
2026-07-27 22:02:57 +02:00
2026-07-08 10:22:00 +02:00
2026-07-08 10:22:00 +02:00
2026-07-27 17:18:00 +02:00
2026-08-05 15:28:23 +02:00
2026-06-12 14:03:41 +02:00
2026-08-03 21:10:11 -07:00
2026-08-12 18:24:31 -07:00
2026-07-03 07:38:16 +02:00
2026-06-03 09:13:00 +02:00
2026-05-28 21:05:01 -07:00
2026-09-04 08:28:47 +02:00
2026-08-23 10:26:44 -07:00
2026-05-11 16:59:43 +02:00
2026-08-11 18:11:20 +02:00
2026-08-11 18:11:20 +02:00
2026-07-15 15:04:55 +02:00
2026-05-19 12:17:36 +02:00
2026-05-24 09:38:47 +02:00
2026-08-25 18:13:37 +03:00
2026-08-25 18:13:35 +03:00
2026-08-25 18:13:36 +03:00
2026-08-25 18:13:35 +03:00
2026-08-25 18:13:37 +03:00
2026-07-28 07:18:48 -04:00
2026-05-21 18:03:06 -04:00
2026-05-21 18:03:07 -04:00
2026-07-07 10:42:29 -04:00
2026-10-02 11:15:22 +02:00
2026-09-23 11:59:31 +02:00
2026-09-25 12:08:43 +02:00
2026-08-24 10:58:57 -07:00
2026-06-21 13:20:19 -07:00
2026-07-22 13:47:02 +02:00
2026-07-31 08:10:49 -06:00
2026-07-31 16:22:52 -04:00
2026-08-03 10:09:08 +02:00
2026-07-13 07:09:28 +02:00
2026-08-03 23:36:18 +02:00
2026-08-06 18:57:25 -07:00
2026-08-05 15:28:23 +02:00
2026-07-15 10:49:03 +02:00
2026-06-29 13:46:50 -06:00
2026-07-14 12:05:01 -03:00
2026-08-19 06:38:45 -04:00
2026-10-06 15:35:40 -07:00
2026-08-19 06:38:44 -04:00
2026-08-24 18:43:15 -07:00
2026-08-24 18:43:00 -07:00
2026-07-30 19:40:28 -07:00
2026-08-24 18:42:56 -07:00
2026-05-20 20:23:32 +02:00
2026-06-15 16:33:40 +02:00
2026-08-20 18:26:42 +02:00
2026-08-20 18:26:42 +02:00
2026-06-08 11:53:18 -07:00
2026-07-03 07:38:16 +02:00
2026-08-17 09:02:07 -07:00
2026-07-28 21:11:55 -07:00
2026-06-06 15:22:44 +02:00
2026-07-03 07:38:16 +02:00