2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-08-22 23:12:11 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2021-04-20 20:21:12 -04:00
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
2021-04-20 20:21:12 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2023-01-03 17:32:16 -05:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
2021-04-20 20:21:12 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-05-28 18:02:38 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
2019-07-03 19:27:42 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2021-04-20 20:21:12 -04:00
|
|
|
|
2023-01-03 17:32:16 -05:00
|
|
|
|
2021-04-20 20:21:12 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2020-06-17 17:33:53 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
2020-06-17 17:33:53 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2021-04-20 20:21:12 -04:00
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2020-06-17 17:33:53 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2021-04-20 20:21:12 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2021-07-10 23:03:15 -04:00
|
|
|
|
2021-04-20 20:21:12 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-03-04 23:05:55 -05:00
|
|
|
|
2023-09-12 18:41:22 -04:00
|
|
|
|
|
|
|
|
|
2021-04-20 20:21:12 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-02-25 13:18:19 -05:00
|
|
|
|
2021-04-20 20:21:12 -04:00
|
|
|
|
2022-02-25 13:18:19 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2021-07-10 23:03:15 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
2023-03-06 02:53:25 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-05-28 18:02:38 -04:00
|
|
|
|
2023-03-06 02:53:25 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
2022-07-20 16:50:26 -04:00
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2022-02-25 13:18:19 -05:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2022-02-25 13:18:19 -05:00
|
|
|
|
|
|
|
|
|
2023-09-19 17:09:22 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2023-09-19 17:09:22 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2023-09-19 17:09:22 -04:00
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
2022-02-25 13:18:19 -05:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-02-25 13:18:19 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-09-12 17:16:02 -04:00
|
|
|
|
2021-08-30 15:18:31 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-06-21 06:44:44 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2019-03-25 15:10:15 -04:00
|
|
|
|
2023-09-12 17:16:02 -04:00
|
|
|
|
|
|
|
|
|
2022-07-20 16:50:26 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-09-12 17:16:02 -04:00
|
|
|
|
2022-07-20 16:50:26 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-09-12 17:16:02 -04:00
|
|
|
|
2023-06-21 06:44:44 -04:00
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
|
|
|
|
|
2021-03-19 20:29:11 -04:00
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-09-12 17:16:02 -04:00
|
|
|
|
2021-08-30 15:18:31 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2022-11-24 03:12:22 -05:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
2023-09-12 17:16:02 -04:00
|
|
|
|
2023-06-21 06:44:44 -04:00
|
|
|
|
2023-09-12 17:16:02 -04:00
|
|
|
|
2019-03-25 15:10:15 -04:00
|
|
|
|
2023-09-12 17:16:02 -04:00
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
2022-11-24 03:12:22 -05:00
|
|
|
|
bcachefs: Start using bpos.snapshot field
This patch starts treating the bpos.snapshot field like part of the key
in the btree code:
* bpos_successor() and bpos_predecessor() now include the snapshot field
* Keys in btrees that will be using snapshots (extents, inodes, dirents
and xattrs) now always have their snapshot field set to U32_MAX
The btree iterator code gets a new flag, BTREE_ITER_ALL_SNAPSHOTS, that
determines whether we're iterating over keys in all snapshots or not -
internally, this controlls whether bkey_(successor|predecessor)
increment/decrement the snapshot field, or only the higher bits of the
key.
We add a new member to struct btree_iter, iter->snapshot: when
BTREE_ITER_ALL_SNAPSHOTS is not set, iter->pos.snapshot should always
equal iter->snapshot, which will be 0 for btrees that don't use
snapshots, and alsways U32_MAX for btrees that will use snapshots
(until we enable snapshot creation).
This patch also introduces a new metadata version number, and compat
code for reading from/writing to older versions - this isn't a forced
upgrade (yet).
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
2021-03-24 18:02:16 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2023-06-21 06:44:44 -04:00
|
|
|
|
2023-09-12 17:16:02 -04:00
|
|
|
|
2023-06-21 06:44:44 -04:00
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2023-09-12 17:16:02 -04:00
|
|
|
|
2021-03-19 20:29:11 -04:00
|
|
|
|
2023-06-21 06:44:44 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-09-12 17:16:02 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-09-12 17:16:02 -04:00
|
|
|
|
2021-08-30 15:18:31 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2023-09-12 17:16:02 -04:00
|
|
|
|
2019-03-25 15:10:15 -04:00
|
|
|
|
2023-09-12 17:16:02 -04:00
|
|
|
|
2022-07-20 16:50:26 -04:00
|
|
|
|
|
|
|
|
|
2021-08-30 15:18:31 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-11-24 03:12:22 -05:00
|
|
|
|
2022-07-20 16:50:26 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-09-12 17:16:02 -04:00
|
|
|
|
2022-07-20 16:50:26 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-09-12 17:16:02 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-02-03 21:01:40 -05:00
|
|
|
|
|
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
2023-02-03 21:01:40 -05:00
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
2023-10-19 22:49:08 -04:00
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
2023-02-03 21:01:40 -05:00
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
2023-02-03 21:01:40 -05:00
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
|
|
|
|
|
2023-02-03 21:01:40 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-10-19 18:31:33 -04:00
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-06-17 20:12:02 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
2023-06-19 21:01:13 -04:00
|
|
|
|
2022-06-17 20:12:02 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-06-19 21:01:13 -04:00
|
|
|
|
|
|
|
|
|
2022-06-17 20:12:02 -04:00
|
|
|
|
bcachefs: Deadlock cycle detector
We've outgrown our own deadlock avoidance strategy.
The btree iterator API provides an interface where the user doesn't need
to concern themselves with lock ordering - different btree iterators can
be traversed in any order. Without special care, this will lead to
deadlocks.
Our previous strategy was to define a lock ordering internally, and
whenever we attempt to take a lock and trylock() fails, we'd check if
the current btree transaction is holding any locks that cause a lock
ordering violation. If so, we'd issue a transaction restart, and then
bch2_trans_begin() would re-traverse all previously used iterators, but
in the correct order.
That approach had some issues, though.
- Sometimes we'd issue transaction restarts unnecessarily, when no
deadlock would have actually occured. Lock ordering restarts have
become our primary cause of transaction restarts, on some workloads
totally 20% of actual transaction commits.
- To avoid deadlock or livelock, we'd often have to take intent locks
when we only wanted a read lock: with the lock ordering approach, it
is actually illegal to hold _any_ read lock while blocking on an intent
lock, and this has been causing us unnecessary lock contention.
- It was getting fragile - the various lock ordering rules are not
trivial, and we'd been seeing occasional livelock issues related to
this machinery.
So, since bcachefs is already a relational database masquerading as a
filesystem, we're stealing the next traditional database technique and
switching to a cycle detector for avoiding deadlocks.
When we block taking a btree lock, after adding ourself to the waitlist
but before sleeping, we do a DFS of btree transactions waiting on other
btree transactions, starting with the current transaction and walking
our held locks, and transactions blocking on our held locks.
If we find a cycle, we emit a transaction restart. Occasionally (e.g.
the btree split path) we can not allow the lock() operation to fail, so
if necessary we'll tell another transaction that it has to fail.
Result: trans_restart_would_deadlock events are reduced by a factor of
10 to 100, and we'll be able to delete a whole bunch of grotty, fragile
code.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
2022-08-22 13:23:47 -04:00
|
|
|
|
2022-06-17 20:12:02 -04:00
|
|
|
|
|
|
|
|
|
2023-06-19 21:01:13 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
2023-06-19 21:01:13 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-06-17 20:12:02 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-02-12 23:15:53 -05:00
|
|
|
|
2022-06-17 20:12:02 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bcachefs: Deadlock cycle detector
We've outgrown our own deadlock avoidance strategy.
The btree iterator API provides an interface where the user doesn't need
to concern themselves with lock ordering - different btree iterators can
be traversed in any order. Without special care, this will lead to
deadlocks.
Our previous strategy was to define a lock ordering internally, and
whenever we attempt to take a lock and trylock() fails, we'd check if
the current btree transaction is holding any locks that cause a lock
ordering violation. If so, we'd issue a transaction restart, and then
bch2_trans_begin() would re-traverse all previously used iterators, but
in the correct order.
That approach had some issues, though.
- Sometimes we'd issue transaction restarts unnecessarily, when no
deadlock would have actually occured. Lock ordering restarts have
become our primary cause of transaction restarts, on some workloads
totally 20% of actual transaction commits.
- To avoid deadlock or livelock, we'd often have to take intent locks
when we only wanted a read lock: with the lock ordering approach, it
is actually illegal to hold _any_ read lock while blocking on an intent
lock, and this has been causing us unnecessary lock contention.
- It was getting fragile - the various lock ordering rules are not
trivial, and we'd been seeing occasional livelock issues related to
this machinery.
So, since bcachefs is already a relational database masquerading as a
filesystem, we're stealing the next traditional database technique and
switching to a cycle detector for avoiding deadlocks.
When we block taking a btree lock, after adding ourself to the waitlist
but before sleeping, we do a DFS of btree transactions waiting on other
btree transactions, starting with the current transaction and walking
our held locks, and transactions blocking on our held locks.
If we find a cycle, we emit a transaction restart. Occasionally (e.g.
the btree split path) we can not allow the lock() operation to fail, so
if necessary we'll tell another transaction that it has to fail.
Result: trans_restart_would_deadlock events are reduced by a factor of
10 to 100, and we'll be able to delete a whole bunch of grotty, fragile
code.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
2022-08-22 13:23:47 -04:00
|
|
|
|
2022-06-17 20:12:02 -04:00
|
|
|
|
2023-06-19 21:01:13 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-06-17 20:12:02 -04:00
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-06-17 20:12:02 -04:00
|
|
|
|
2022-08-14 16:11:35 -04:00
|
|
|
|
2022-06-17 20:12:02 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-07-14 20:33:09 +12:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-08-11 19:36:24 -04:00
|
|
|
|
2022-07-14 20:33:09 +12:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-08-11 21:06:02 -04:00
|
|
|
|
2022-08-11 19:36:24 -04:00
|
|
|
|
|
|
|
|
|
2022-07-14 20:33:09 +12:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-10-17 07:03:11 -04:00
|
|
|
|
|
|
|
|
|
2022-08-11 21:06:02 -04:00
|
|
|
|
|
|
|
|
|
2022-10-17 07:03:11 -04:00
|
|
|
|
2022-07-14 20:33:09 +12:00
|
|
|
|
2022-08-11 19:36:24 -04:00
|
|
|
|
2022-08-11 20:14:54 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-08-22 21:49:55 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-08-11 20:14:54 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-08-11 19:36:24 -04:00
|
|
|
|
2022-07-14 20:33:09 +12:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-08-22 23:12:11 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-06-19 21:01:13 -04:00
|
|
|
|
2022-08-22 23:12:11 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-06-19 21:01:13 -04:00
|
|
|
|
|
|
|
|
|
2022-10-02 01:41:08 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-06-19 21:01:13 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-10-02 01:41:08 -04:00
|
|
|
|
2023-06-19 21:01:13 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-10-02 01:41:08 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-06-19 21:01:13 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-10-02 01:41:08 -04:00
|
|
|
|
2023-06-19 21:01:13 -04:00
|
|
|
|
2022-08-22 23:12:11 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-06-17 20:12:02 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-08-11 20:14:54 -04:00
|
|
|
|
|
|
|
|
|
2022-07-14 20:33:09 +12:00
|
|
|
|
2022-08-22 23:12:11 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-10-19 22:49:08 -04:00
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
2023-10-19 22:49:08 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
2023-10-19 22:49:08 -04:00
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
2022-02-26 11:48:34 -05:00
|
|
|
|
|
|
|
|
|
2017-03-16 22:18:50 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|