Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1269581
| From | Ben Hutchings <ben@decadent.org.uk> |
|---|---|
| Newsgroups | linux.kernel |
| Subject | [PATCH 3.2 43/60] dm btree remove: fix a bug when rebalancing nodes after removal |
| Date | 2015-11-15 03:10 +0100 |
| Message-ID | <quUVt-3GF-45@gated-at.bofh.it> (permalink) |
| References | <quUVr-3GF-3@gated-at.bofh.it> |
| Organization | linux.* mail to news gateway |
3.2.73-rc1 review patch. If anyone has any objections, please let me know.
------------------
From: Joe Thornber <ejt@redhat.com>
commit 2871c69e025e8bc507651d5a9cf81a8a7da9d24b upstream.
Commit 4c7e309340ff ("dm btree remove: fix bug in redistribute3") wasn't
a complete fix for redistribute3().
The redistribute3 function takes 3 btree nodes and shares out the entries
evenly between them. If the three nodes in total contained
(MAX_ENTRIES * 3) - 1 entries between them then this was erroneously getting
rebalanced as (MAX_ENTRIES - 1) on the left and right, and (MAX_ENTRIES + 1) in
the center.
Fix this issue by being more careful about calculating the target number
of entries for the left and right nodes.
Unit tested in userspace using this program:
https://github.com/jthornber/redistribute3-test/blob/master/redistribute3_t.c
Signed-off-by: Joe Thornber <ejt@redhat.com>
Signed-off-by: Mike Snitzer <snitzer@redhat.com>
Signed-off-by: Ben Hutchings <ben@decadent.org.uk>
---
drivers/md/persistent-data/dm-btree-remove.c | 17 +++++++++++------
1 file changed, 11 insertions(+), 6 deletions(-)
--- a/drivers/md/persistent-data/dm-btree-remove.c
+++ b/drivers/md/persistent-data/dm-btree-remove.c
@@ -301,11 +301,16 @@ static void redistribute3(struct dm_btre
{
int s;
uint32_t max_entries = le32_to_cpu(left->header.max_entries);
- unsigned target = (nr_left + nr_center + nr_right) / 3;
- BUG_ON(target > max_entries);
+ unsigned total = nr_left + nr_center + nr_right;
+ unsigned target_right = total / 3;
+ unsigned remainder = (target_right * 3) != total;
+ unsigned target_left = target_right + remainder;
+
+ BUG_ON(target_left > max_entries);
+ BUG_ON(target_right > max_entries);
if (nr_left < nr_right) {
- s = nr_left - target;
+ s = nr_left - target_left;
if (s < 0 && nr_center < -s) {
/* not enough in central node */
@@ -316,10 +321,10 @@ static void redistribute3(struct dm_btre
} else
shift(left, center, s);
- shift(center, right, target - nr_right);
+ shift(center, right, target_right - nr_right);
} else {
- s = target - nr_right;
+ s = target_right - nr_right;
if (s > 0 && nr_center < s) {
/* not enough in central node */
shift(center, right, nr_center);
@@ -329,7 +334,7 @@ static void redistribute3(struct dm_btre
} else
shift(center, right, s);
- shift(left, center, nr_left - target);
+ shift(left, center, nr_left - target_left);
}
*key_ptr(parent, c->index) = center->keys[0];
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
[PATCH 3.2 00/60] 3.2.73-rc1 review Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:10 +0100
[PATCH 3.2 43/60] dm btree remove: fix a bug when rebalancing nodes after removal Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:10 +0100
[PATCH 3.2 27/60] 3w-9xxx: don't unmap bounce buffered commands Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:10 +0100
[PATCH 3.2 12/60] genirq: Fix race in register_irq_proc() Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:10 +0100
[PATCH 3.2 31/60] iommu/vt-d: fix range computation when making room for large pages Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:10 +0100
[PATCH 3.2 28/60] xen-blkfront: check for null drvdata in blkback_changed (XenbusStateClosing) Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:10 +0100
[PATCH 3.2 32/60] xhci: don't finish a TD if we get a short transfer event mid TD Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:10 +0100
[PATCH 3.2 46/60] md/raid1: don't clear bitmap bit when bad-block-list write fails. Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:10 +0100
[PATCH 3.2 24/60] iwlwifi: dvm: fix D3 firmware PN programming Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:10 +0100
[PATCH 3.2 04/60] regmap: debugfs: Don't bother actually printing when calculating max length Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:10 +0100
[PATCH 3.2 55/60] asix: Don't reset PHY on if_up for ASIX 88772 Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 08/60] UBI: Validate data_size Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 53/60] skbuff: Fix skb checksum partial check. Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 38/60] IB/cm: Fix rb-tree duplicate free and use-after-free Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 20/60] usb: Add device quirk for Logitech PTZ cameras Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 33/60] xhci: handle no ping response error properly Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 19/60] USB: Add reset-resume quirk for two Plantronics usb headphones. Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 44/60] dm btree: fix leak of bufio-backed block in btree_split_beneath error path Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 40/60] powerpc/rtas: Validate rtas.entry before calling enter_rtas() Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 34/60] xhci: Switch Intel Lynx Point LP ports to EHCI on shutdown. Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 07/60] x86/xen: Do not clip xen_e820_map to xen_e820_map_entries when sanitizing map Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 03/60] regmap: debugfs: Ensure we don't underflow when printing access masks Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 51/60] net: add length argument to skb_copy_and_csum_datagram_iovec Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 05/60] ath9k: declare required extra tx headroom Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 39/60] drm/nouveau/gem: return only valid domain when there's only one Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 06/60] m68k: Define asmlinkage_protect Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 26/60] sched/core: Fix TASK_DEAD race in finish_task_switch() Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 45/60] md/raid1: ensure device failure recorded before write request returns. Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 15/60] md/raid0: update queue parameter in a safer location. Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 59/60] KEYS: Fix race between key destruction and finding a keyring by name Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 23/60] ppp: don't override sk->sk_state in pppoe_flush_dev() Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 49/60] mvsas: Fix NULL pointer dereference in mvs_slot_task_free Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 58/60] KVM: x86: work around infinite loop in microcode when #AC is delivered Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:20 +0100
[PATCH 3.2 42/60] ppp: fix pppoe_dev deletion condition in pppoe_release() Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:30 +0100
[PATCH 3.2 10/60] MIPS: dma-default: Fix 32-bit fall back to GFP_DMA Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:30 +0100
[PATCH 3.2 50/60] sched: declare pid_alive as inline Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:30 +0100
[PATCH 3.2 17/60] clocksource: Fix abs() usage w/ 64bit values Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:30 +0100
[PATCH 3.2 36/60] crypto: api - Only abort operations on fatal signal Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:30 +0100
[PATCH 3.2 16/60] md/raid0: apply base queue limits *before* disk_stack_limits Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:30 +0100
[PATCH 3.2 47/60] md/raid10: ensure device failure recorded before write request returns. Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:30 +0100
[PATCH 3.2 57/60] Failing to send a CLOSE if file is opened WRONLY and server reboots on a 4.x mount Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:30 +0100
[PATCH 3.2 14/60] [SMB3] Do not fall back to SMBWriteX in set_file_size error cases Ben Hutchings <ben@decadent.org.uk> - 2015-11-15 03:30 +0100
Re: [PATCH 3.2 00/60] 3.2.73-rc1 review Guenter Roeck <linux@roeck-us.net> - 2015-11-15 14:50 +0100
Re: [PATCH 3.2 00/60] 3.2.73-rc1 review Ben Hutchings <ben@decadent.org.uk> - 2015-11-16 12:20 +0100
csiph-web