Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1269267
| From | Kamal Mostafa <kamal@canonical.com> |
|---|---|
| Newsgroups | linux.kernel |
| Subject | [PATCH 3.13.y-ckt 80/96] dm btree remove: fix a bug when rebalancing nodes after removal |
| Date | 2015-11-13 23:00 +0100 |
| Message-ID | <quuy1-3qR-67@gated-at.bofh.it> (permalink) |
| References | <quuxY-3qR-3@gated-at.bofh.it> |
| Organization | linux.* mail to news gateway |
3.13.11-ckt30 -stable 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: Kamal Mostafa <kamal@canonical.com>
---
drivers/md/persistent-data/dm-btree-remove.c | 17 +++++++++++------
1 file changed, 11 insertions(+), 6 deletions(-)
diff --git a/drivers/md/persistent-data/dm-btree-remove.c b/drivers/md/persistent-data/dm-btree-remove.c
index 7c0d755..92cd09f 100644
--- 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_btree_info *info, struct btree_node *parent,
{
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_btree_info *info, struct btree_node *parent,
} 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_btree_info *info, struct btree_node *parent,
} 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];
--
1.9.1
--
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
[3.13.y-ckt stable] Linux 3.13.11-ckt30 stable review Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:00 +0100 [PATCH 3.13.y-ckt 83/96] module: Fix locking in symbol_put_addr() Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:00 +0100 [PATCH 3.13.y-ckt 80/96] dm btree remove: fix a bug when rebalancing nodes after removal Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:00 +0100 [PATCH 3.13.y-ckt 82/96] IB/cm: Fix rb-tree duplicate free and use-after-free Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:00 +0100 [PATCH 3.13.y-ckt 96/96] ppp: fix pppoe_dev deletion condition in pppoe_release() Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:00 +0100 [PATCH 3.13.y-ckt 57/96] ethtool: Use kcalloc instead of kmalloc for ethtool_get_strings Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:00 +0100 [PATCH 3.13.y-ckt 85/96] md/raid1: submit_bio_wait() returns 0 on success Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:00 +0100 [PATCH 3.13.y-ckt 42/96] crypto: ahash - ensure statesize is non-zero Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 61/96] iio: accel: sca3000: memory corruption in sca3000_read_first_n_hw_rb() Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 64/96] iwlwifi: fix firmware filename for 3160 Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 53/96] skbuff: Fix skb checksum flag on skb pull Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 62/96] iwlwifi: dvm: fix D3 firmware PN programming Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 50/96] af_unix: Convert the unix_sk macro to an inline function for type safety Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 54/96] skbuff: Fix skb checksum partial check. Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 47/96] i2c: designware-platdrv: enable RuntimePM before registering to the core Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 37/96] mm/slab: fix unexpected index mapping result of kmalloc_size(INDEX_NODE+1) Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 35/96] dmaengine: dw: properly read DWC_PARAMS register Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 74/96] drm/nouveau/gem: return only valid domain when there's only one Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 51/96] af_unix: return data from multiple SKBs on recv() with MSG_PEEK flag Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 65/96] iwlwifi: pci: add a few more PCI subvendor IDs for the 7265 series Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 69/96] ASoC: Add info callback for SX_TLV controls Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 55/96] net: add pfmemalloc check in sk_add_backlog() Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 70/96] xhci: don't finish a TD if we get a short transfer event mid TD Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 71/96] xhci: handle no ping response error properly Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 49/96] l2tp: protect tunnel->del_work by ref_count Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 48/96] i2c: designware: Do not use parameters from ACPI on Dell Inspiron 7348 Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 46/96] i2c: s3c2410: enable RuntimePM before registering to the core Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 45/96] i2c: rcar: enable RuntimePM before registering to the core Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 44/96] btrfs: fix use after free iterating extrefs Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 68/96] ALSA: hda - Fix inverted internal mic on Lenovo G50-80 Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 67/96] xen-blkfront: check for null drvdata in blkback_changed (XenbusStateClosing) Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 52/96] net/unix: fix logic about sk_peek_offset Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:10 +0100 [PATCH 3.13.y-ckt 19/96] KVM: nSVM: Check for NRIPS support before updating control field Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 28/96] ALSA: hda - Apply SPDIF pin ctl to MacBookPro 12,1 Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 36/96] 3w-9xxx: don't unmap bounce buffered commands Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 26/96] dm raid: fix round up of default region size Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 29/96] USB: Add reset-resume quirk for two Plantronics usb headphones. Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 12/96] UBI: return ENOSPC if no enough space available Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 20/96] Use WARN_ON_ONCE for missing X86_FEATURE_NRIPS Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 30/96] usb: Add device quirk for Logitech PTZ cameras Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 16/96] Initialize msg/shm IPC objects before doing ipc_addid() Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 34/96] dm cache: fix NULL pointer when switching from cleaner policy Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 39/96] crypto: sparc - initialize blkcipher.ivsize Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 18/96] genirq: Fix race in register_irq_proc() Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 01/96] isdn_ppp: Add checks for allocation failure in isdn_ppp_open() Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 17/96] drm/qxl: recreate the primary surface when the bo is not primary Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 11/96] x86/xen: Do not clip xen_e820_map to xen_e820_map_entries when sanitizing map Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 10/96] x86/xen: Support kexec/kdump in HVM guests by doing a soft reset Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 25/96] ASoC: dwc: correct irq clear method Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 15/96] MIPS: dma-default: Fix 32-bit fall back to GFP_DMA Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 24/96] x86/mm: Set NX on gap between __ex_table and rodata Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 27/96] clocksource: Fix abs() usage w/ 64bit values Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 13/96] s390/boot: fix boot of compressed kernel built with gcc 4.9 Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 22/96] mm: hugetlbfs: skip shared VMAs when unmapping private pages to satisfy a fault Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 43/96] dm thin: fix missing pool reference count decrement in pool_ctr error path Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 31/96] staging: speakup: fix speakup-r regression Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 32/96] ALSA: synth: Fix conflicting OSS device registration on AWE32 Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 23/96] [SMB3] Do not fall back to SMBWriteX in set_file_size error cases Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 38/96] workqueue: make sure delayed work run in local cpu Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 21/96] dm: fix AB-BA deadlock in __dm_destroy() Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 41/96] arm64: errata: use KBUILD_CFLAGS_MODULE for erratum #843419 Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 06/96] tools lib traceevent: Fix string handling in heterogeneous arch environments Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:20 +0100 [PATCH 3.13.y-ckt 07/96] perf tools: Fix copying of /proc/kcore Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:30 +0100 [PATCH 3.13.y-ckt 02/96] ppp, slip: Validate VJ compression slot parameters completely Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:30 +0100 [PATCH 3.13.y-ckt 09/96] m68k: Define asmlinkage_protect Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:30 +0100 [PATCH 3.13.y-ckt 03/96] staging/dgnc: fix info leak in ioctl Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:30 +0100 [PATCH 3.13.y-ckt 05/96] regmap: debugfs: Don't bother actually printing when calculating max length Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:30 +0100 [PATCH 3.13.y-ckt 04/96] regmap: debugfs: Ensure we don't underflow when printing access masks Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:30 +0100 [PATCH 3.13.y-ckt 08/96] ASoC: db1200: Fix DAI link format for db1300 and db1550 Kamal Mostafa <kamal@canonical.com> - 2015-11-13 23:30 +0100
csiph-web