From 3b5d56b9317fa7b5407dff1aa7b115bf6cdbd494 Mon Sep 17 00:00:00 2001 From: Eric B Munson Date: Sat, 10 Mar 2012 14:37:26 -0500 Subject: kvmclock: Add functions to check if the host has stopped the vm When a host stops or suspends a VM it will set a flag to show this. The watchdog will use these functions to determine if a softlockup is real, or the result of a suspended VM. Signed-off-by: Eric B Munson asm-generic changes Acked-by: Arnd Bergmann Signed-off-by: Marcelo Tosatti Signed-off-by: Avi Kivity --- include/asm-generic/kvm_para.h | 14 ++++++++++++++ 1 file changed, 14 insertions(+) create mode 100644 include/asm-generic/kvm_para.h (limited to 'include/asm-generic') diff --git a/include/asm-generic/kvm_para.h b/include/asm-generic/kvm_para.h new file mode 100644 index 000000000000..05ef7e705939 --- /dev/null +++ b/include/asm-generic/kvm_para.h @@ -0,0 +1,14 @@ +#ifndef _ASM_GENERIC_KVM_PARA_H +#define _ASM_GENERIC_KVM_PARA_H + + +/* + * This function is used by architectures that support kvm to avoid issuing + * false soft lockup messages. + */ +static inline bool kvm_check_and_clear_guest_paused(void) +{ + return false; +} + +#endif -- cgit v1.2.3-70-g09d2 From 1f15d10984c854e077da5aa1a23f901496b49773 Mon Sep 17 00:00:00 2001 From: Marcelo Tosatti Date: Fri, 20 Apr 2012 18:21:46 -0300 Subject: KVM: add kvm_arch_para_features stub to asm-generic/kvm_para.h Needed by kvm_para_has_feature(). Reported-by: Stephen Rothwell Signed-off-by: Marcelo Tosatti --- include/asm-generic/kvm_para.h | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'include/asm-generic') diff --git a/include/asm-generic/kvm_para.h b/include/asm-generic/kvm_para.h index 05ef7e705939..9a7bbadb688d 100644 --- a/include/asm-generic/kvm_para.h +++ b/include/asm-generic/kvm_para.h @@ -11,4 +11,9 @@ static inline bool kvm_check_and_clear_guest_paused(void) return false; } +static inline unsigned int kvm_arch_para_features(void) +{ + return 0; +} + #endif -- cgit v1.2.3-70-g09d2 From 09d71ff19404b3957fab6de942fb8026ccfd8524 Mon Sep 17 00:00:00 2001 From: Mark Brown Date: Wed, 2 May 2012 12:46:46 +0100 Subject: gpiolib: Implement devm_gpio_request_one() Allow drivers to use the modern request and configure idiom together with devres. As with plain gpio_request() and gpio_request_one() we can't implement the old school version in terms of _one() as this would force the explicit selection of a direction in gpio_request() which could break systems if we pick the wrong one. Implementing devm_gpio_request_one() in terms of devm_gpio_request() would needlessly complicate things or lead to duplication from the unmanaged version depending on how it's done. Signed-off-by: Mark Brown Acked-by: Linus Walleij Signed-off-by: Grant Likely --- drivers/gpio/devres.c | 29 +++++++++++++++++++++++++++++ include/asm-generic/gpio.h | 2 ++ include/linux/gpio.h | 6 ++++++ 3 files changed, 37 insertions(+) (limited to 'include/asm-generic') diff --git a/drivers/gpio/devres.c b/drivers/gpio/devres.c index 3dd29399cef5..d21a9ff38551 100644 --- a/drivers/gpio/devres.c +++ b/drivers/gpio/devres.c @@ -70,6 +70,35 @@ int devm_gpio_request(struct device *dev, unsigned gpio, const char *label) } EXPORT_SYMBOL(devm_gpio_request); +/** + * devm_gpio_request_one - request a single GPIO with initial setup + * @dev: device to request for + * @gpio: the GPIO number + * @flags: GPIO configuration as specified by GPIOF_* + * @label: a literal description string of this GPIO + */ +int devm_gpio_request_one(struct device *dev, unsigned gpio, + unsigned long flags, const char *label) +{ + unsigned *dr; + int rc; + + dr = devres_alloc(devm_gpio_release, sizeof(unsigned), GFP_KERNEL); + if (!dr) + return -ENOMEM; + + rc = gpio_request_one(gpio, flags, label); + if (rc) { + devres_free(dr); + return rc; + } + + *dr = gpio; + devres_add(dev, dr); + + return 0; +} + /** * devm_gpio_free - free an interrupt * @dev: device to free gpio for diff --git a/include/asm-generic/gpio.h b/include/asm-generic/gpio.h index 5f52690c3c8f..4ead12332c66 100644 --- a/include/asm-generic/gpio.h +++ b/include/asm-generic/gpio.h @@ -179,6 +179,8 @@ extern void gpio_free_array(const struct gpio *array, size_t num); /* bindings for managed devices that want to request gpios */ int devm_gpio_request(struct device *dev, unsigned gpio, const char *label); +int devm_gpio_request_one(struct device *dev, unsigned gpio, + unsigned long flags, const char *label); void devm_gpio_free(struct device *dev, unsigned int gpio); #ifdef CONFIG_GPIO_SYSFS diff --git a/include/linux/gpio.h b/include/linux/gpio.h index 7a8816a1a0d8..f07fc2d08159 100644 --- a/include/linux/gpio.h +++ b/include/linux/gpio.h @@ -106,6 +106,12 @@ static inline int gpio_request_one(unsigned gpio, return -ENOSYS; } +static inline int devm_gpio_request_one(struct device *dev, unsigned gpio, + unsigned long flags, const char *label) +{ + return -ENOSYS; +} + static inline int gpio_request_array(const struct gpio *array, size_t num) { return -ENOSYS; -- cgit v1.2.3-70-g09d2 From 3d0f7cf0f3633f92ddeb767eb59cab73963d4dee Mon Sep 17 00:00:00 2001 From: Grant Likely Date: Thu, 17 May 2012 13:54:40 -0600 Subject: gpio: Adjust of_xlate API to support multiple GPIO chips This patch changes the of_xlate API to make it possible for multiple gpio_chips to refer to the same device tree node. This is useful for banked GPIO controllers that use multiple gpio_chips for a single device. With this change the core code will try calling of_xlate on each gpio_chip that references the device_node and will return the gpio number for the first one to return 'true'. Tested-by: Roland Stigge Acked-by: Arnd Bergmann Signed-off-by: Grant Likely --- arch/arm/mach-imx/mach-mx35_3ds.c | 3 +- drivers/gpio/gpiolib-of.c | 80 +++++++++++++++++++-------------------- drivers/gpio/gpiolib.c | 2 +- include/asm-generic/gpio.h | 2 +- include/linux/of_gpio.h | 1 - 5 files changed, 41 insertions(+), 47 deletions(-) (limited to 'include/asm-generic') diff --git a/arch/arm/mach-imx/mach-mx35_3ds.c b/arch/arm/mach-imx/mach-mx35_3ds.c index 6ae51c6b95b7..6a7cf91ee819 100644 --- a/arch/arm/mach-imx/mach-mx35_3ds.c +++ b/arch/arm/mach-imx/mach-mx35_3ds.c @@ -96,8 +96,7 @@ static struct i2c_board_info __initdata i2c_devices_3ds[] = { static int lcd_power_gpio = -ENXIO; -static int mc9s08dz60_gpiochip_match(struct gpio_chip *chip, - const void *data) +static int mc9s08dz60_gpiochip_match(struct gpio_chip *chip, void *data) { return !strcmp(chip->label, data); } diff --git a/drivers/gpio/gpiolib-of.c b/drivers/gpio/gpiolib-of.c index bf984b6dc477..d18068a9f3ec 100644 --- a/drivers/gpio/gpiolib-of.c +++ b/drivers/gpio/gpiolib-of.c @@ -15,11 +15,39 @@ #include #include #include +#include #include #include #include #include +/* Private data structure for of_gpiochip_is_match */ +struct gg_data { + enum of_gpio_flags *flags; + struct of_phandle_args gpiospec; + + int out_gpio; +}; + +/* Private function for resolving node pointer to gpio_chip */ +static int of_gpiochip_find_and_xlate(struct gpio_chip *gc, void *data) +{ + struct gg_data *gg_data = data; + int ret; + + if ((gc->of_node != gg_data->gpiospec.np) || + (gc->of_gpio_n_cells != gg_data->gpiospec.args_count) || + (!gc->of_xlate)) + return false; + + ret = gc->of_xlate(gc, &gg_data->gpiospec, gg_data->flags); + if (ret < 0) + return false; + + gg_data->out_gpio = ret + gc->base; + return true; +} + /** * of_get_named_gpio_flags() - Get a GPIO number and flags to use with GPIO API * @np: device node to get GPIO from @@ -34,46 +62,25 @@ int of_get_named_gpio_flags(struct device_node *np, const char *propname, int index, enum of_gpio_flags *flags) { + struct gg_data gg_data = { .flags = flags, .out_gpio = -ENODEV }; int ret; - struct gpio_chip *gc; - struct of_phandle_args gpiospec; + + /* .of_xlate might decide to not fill in the flags, so clear it. */ + if (flags) + *flags = 0; ret = of_parse_phandle_with_args(np, propname, "#gpio-cells", index, - &gpiospec); + &gg_data.gpiospec); if (ret) { pr_debug("%s: can't parse gpios property\n", __func__); - goto err0; - } - - gc = of_node_to_gpiochip(gpiospec.np); - if (!gc) { - pr_debug("%s: gpio controller %s isn't registered\n", - np->full_name, gpiospec.np->full_name); - ret = -ENODEV; - goto err1; - } - - if (gpiospec.args_count != gc->of_gpio_n_cells) { - pr_debug("%s: wrong #gpio-cells for %s\n", - np->full_name, gpiospec.np->full_name); - ret = -EINVAL; - goto err1; + return -EINVAL; } - /* .xlate might decide to not fill in the flags, so clear it. */ - if (flags) - *flags = 0; - - ret = gc->of_xlate(gc, &gpiospec, flags); - if (ret < 0) - goto err1; + gpiochip_find(&gg_data, of_gpiochip_find_and_xlate); - ret += gc->base; -err1: - of_node_put(gpiospec.np); -err0: + of_node_put(gg_data.gpiospec.np); pr_debug("%s exited with status %d\n", __func__, ret); - return ret; + return gg_data.out_gpio; } EXPORT_SYMBOL(of_get_named_gpio_flags); @@ -227,14 +234,3 @@ void of_gpiochip_remove(struct gpio_chip *chip) if (chip->of_node) of_node_put(chip->of_node); } - -/* Private function for resolving node pointer to gpio_chip */ -static int of_gpiochip_is_match(struct gpio_chip *chip, const void *data) -{ - return chip->of_node == data; -} - -struct gpio_chip *of_node_to_gpiochip(struct device_node *np) -{ - return gpiochip_find(np, of_gpiochip_is_match); -} diff --git a/drivers/gpio/gpiolib.c b/drivers/gpio/gpiolib.c index 566d0122d832..38353c028fdd 100644 --- a/drivers/gpio/gpiolib.c +++ b/drivers/gpio/gpiolib.c @@ -1156,7 +1156,7 @@ EXPORT_SYMBOL_GPL(gpiochip_remove); */ struct gpio_chip *gpiochip_find(const void *data, int (*match)(struct gpio_chip *chip, - const void *data)) + void *data)) { struct gpio_chip *chip = NULL; unsigned long flags; diff --git a/include/asm-generic/gpio.h b/include/asm-generic/gpio.h index 4ead12332c66..1ba08f0e49a3 100644 --- a/include/asm-generic/gpio.h +++ b/include/asm-generic/gpio.h @@ -144,7 +144,7 @@ extern int gpiochip_add(struct gpio_chip *chip); extern int __must_check gpiochip_remove(struct gpio_chip *chip); extern struct gpio_chip *gpiochip_find(const void *data, int (*match)(struct gpio_chip *chip, - const void *data)); + void *data)); /* Always use the library code for GPIO management calls, diff --git a/include/linux/of_gpio.h b/include/linux/of_gpio.h index 81733d12cbea..c454f5796747 100644 --- a/include/linux/of_gpio.h +++ b/include/linux/of_gpio.h @@ -58,7 +58,6 @@ extern int of_mm_gpiochip_add(struct device_node *np, extern void of_gpiochip_add(struct gpio_chip *gc); extern void of_gpiochip_remove(struct gpio_chip *gc); -extern struct gpio_chip *of_node_to_gpiochip(struct device_node *np); extern int of_gpio_simple_xlate(struct gpio_chip *gc, const struct of_phandle_args *gpiospec, u32 *flags); -- cgit v1.2.3-70-g09d2 From 07ce8ec7308ab3fa55fe2861671b157f857fff58 Mon Sep 17 00:00:00 2001 From: Grant Likely Date: Fri, 18 May 2012 23:01:05 -0600 Subject: gpiolib: Remove 'const' from data argument of gpiochip_find() Commit 3d0f7cf0 "gpio: Adjust of_xlate API to support multiple GPIO chips" changed the api of gpiochip_find to drop const from the data parameter of the match hook, but didn't also drop const from data causing a build warning. Signed-off-by: Grant Likely --- drivers/gpio/gpiolib.c | 2 +- include/asm-generic/gpio.h | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) (limited to 'include/asm-generic') diff --git a/drivers/gpio/gpiolib.c b/drivers/gpio/gpiolib.c index e48b70c6ddf1..120b2a0e3167 100644 --- a/drivers/gpio/gpiolib.c +++ b/drivers/gpio/gpiolib.c @@ -1154,7 +1154,7 @@ EXPORT_SYMBOL_GPL(gpiochip_remove); * non-zero, this function will return to the caller and not iterate over any * more gpio_chips. */ -struct gpio_chip *gpiochip_find(const void *data, +struct gpio_chip *gpiochip_find(void *data, int (*match)(struct gpio_chip *chip, void *data)) { diff --git a/include/asm-generic/gpio.h b/include/asm-generic/gpio.h index 1ba08f0e49a3..365ea09ed3b0 100644 --- a/include/asm-generic/gpio.h +++ b/include/asm-generic/gpio.h @@ -142,7 +142,7 @@ extern int __must_check gpiochip_reserve(int start, int ngpio); /* add/remove chips */ extern int gpiochip_add(struct gpio_chip *chip); extern int __must_check gpiochip_remove(struct gpio_chip *chip); -extern struct gpio_chip *gpiochip_find(const void *data, +extern struct gpio_chip *gpiochip_find(void *data, int (*match)(struct gpio_chip *chip, void *data)); -- cgit v1.2.3-70-g09d2 From bca0fa5f12a6744a2b2e53154af65a51402b3426 Mon Sep 17 00:00:00 2001 From: Marek Szyprowski Date: Fri, 23 Mar 2012 13:05:14 +0100 Subject: common: add dma_mmap_from_coherent() function Add a common helper for dma-mapping core for mapping a coherent buffer to userspace. Reported-by: Subash Patel Signed-off-by: Marek Szyprowski Acked-by: Kyungmin Park Tested-By: Subash Patel --- drivers/base/dma-coherent.c | 42 ++++++++++++++++++++++++++++++++++++++ include/asm-generic/dma-coherent.h | 4 +++- 2 files changed, 45 insertions(+), 1 deletion(-) (limited to 'include/asm-generic') diff --git a/drivers/base/dma-coherent.c b/drivers/base/dma-coherent.c index bb0025c510b3..1b85949e3d2f 100644 --- a/drivers/base/dma-coherent.c +++ b/drivers/base/dma-coherent.c @@ -10,6 +10,7 @@ struct dma_coherent_mem { void *virt_base; dma_addr_t device_base; + phys_addr_t pfn_base; int size; int flags; unsigned long *bitmap; @@ -44,6 +45,7 @@ int dma_declare_coherent_memory(struct device *dev, dma_addr_t bus_addr, dev->dma_mem->virt_base = mem_base; dev->dma_mem->device_base = device_addr; + dev->dma_mem->pfn_base = PFN_DOWN(bus_addr); dev->dma_mem->size = pages; dev->dma_mem->flags = flags; @@ -176,3 +178,43 @@ int dma_release_from_coherent(struct device *dev, int order, void *vaddr) return 0; } EXPORT_SYMBOL(dma_release_from_coherent); + +/** + * dma_mmap_from_coherent() - try to mmap the memory allocated from + * per-device coherent memory pool to userspace + * @dev: device from which the memory was allocated + * @vma: vm_area for the userspace memory + * @vaddr: cpu address returned by dma_alloc_from_coherent + * @size: size of the memory buffer allocated by dma_alloc_from_coherent + * + * This checks whether the memory was allocated from the per-device + * coherent memory pool and if so, maps that memory to the provided vma. + * + * Returns 1 if we correctly mapped the memory, or 0 if + * dma_release_coherent() should proceed with mapping memory from + * generic pools. + */ +int dma_mmap_from_coherent(struct device *dev, struct vm_area_struct *vma, + void *vaddr, size_t size, int *ret) +{ + struct dma_coherent_mem *mem = dev ? dev->dma_mem : NULL; + + if (mem && vaddr >= mem->virt_base && vaddr + size <= + (mem->virt_base + (mem->size << PAGE_SHIFT))) { + unsigned long off = vma->vm_pgoff; + int start = (vaddr - mem->virt_base) >> PAGE_SHIFT; + int user_count = (vma->vm_end - vma->vm_start) >> PAGE_SHIFT; + int count = size >> PAGE_SHIFT; + + *ret = -ENXIO; + if (off < count && user_count <= count - off) { + unsigned pfn = mem->pfn_base + start + off; + *ret = remap_pfn_range(vma, vma->vm_start, pfn, + user_count << PAGE_SHIFT, + vma->vm_page_prot); + } + return 1; + } + return 0; +} +EXPORT_SYMBOL(dma_mmap_from_coherent); diff --git a/include/asm-generic/dma-coherent.h b/include/asm-generic/dma-coherent.h index 85a3ffaa0242..abfb2682de7f 100644 --- a/include/asm-generic/dma-coherent.h +++ b/include/asm-generic/dma-coherent.h @@ -3,13 +3,15 @@ #ifdef CONFIG_HAVE_GENERIC_DMA_COHERENT /* - * These two functions are only for dma allocator. + * These three functions are only for dma allocator. * Don't use them in device drivers. */ int dma_alloc_from_coherent(struct device *dev, ssize_t size, dma_addr_t *dma_handle, void **ret); int dma_release_from_coherent(struct device *dev, int order, void *vaddr); +int dma_mmap_from_coherent(struct device *dev, struct vm_area_struct *vma, + void *cpu_addr, size_t size, int *ret); /* * Standard interface */ -- cgit v1.2.3-70-g09d2 From c64be2bb1c6eb43c838b2c6d57b074078be208dd Mon Sep 17 00:00:00 2001 From: Marek Szyprowski Date: Thu, 29 Dec 2011 13:09:51 +0100 Subject: drivers: add Contiguous Memory Allocator The Contiguous Memory Allocator is a set of helper functions for DMA mapping framework that improves allocations of contiguous memory chunks. CMA grabs memory on system boot, marks it with MIGRATE_CMA migrate type and gives back to the system. Kernel is allowed to allocate only movable pages within CMA's managed memory so that it can be used for example for page cache when DMA mapping do not use it. On dma_alloc_from_contiguous() request such pages are migrated out of CMA area to free required contiguous block and fulfill the request. This allows to allocate large contiguous chunks of memory at any time assuming that there is enough free memory available in the system. This code is heavily based on earlier works by Michal Nazarewicz. Signed-off-by: Marek Szyprowski Signed-off-by: Kyungmin Park Signed-off-by: Michal Nazarewicz Acked-by: Arnd Bergmann Tested-by: Rob Clark Tested-by: Ohad Ben-Cohen Tested-by: Benjamin Gaignard Tested-by: Robert Nelson Tested-by: Barry Song --- Documentation/kernel-parameters.txt | 5 + arch/Kconfig | 3 + drivers/base/Kconfig | 89 ++++++++ drivers/base/Makefile | 1 + drivers/base/dma-contiguous.c | 401 +++++++++++++++++++++++++++++++++++ include/asm-generic/dma-contiguous.h | 28 +++ include/linux/device.h | 4 + include/linux/dma-contiguous.h | 110 ++++++++++ 8 files changed, 641 insertions(+) create mode 100644 drivers/base/dma-contiguous.c create mode 100644 include/asm-generic/dma-contiguous.h create mode 100644 include/linux/dma-contiguous.h (limited to 'include/asm-generic') diff --git a/Documentation/kernel-parameters.txt b/Documentation/kernel-parameters.txt index c1601e5a8b71..669e8bb52b94 100644 --- a/Documentation/kernel-parameters.txt +++ b/Documentation/kernel-parameters.txt @@ -508,6 +508,11 @@ bytes respectively. Such letter suffixes can also be entirely omitted. Also note the kernel might malfunction if you disable some critical bits. + cma=nn[MG] [ARM,KNL] + Sets the size of kernel global memory area for contiguous + memory allocations. For more information, see + include/linux/dma-contiguous.h + cmo_free_hint= [PPC] Format: { yes | no } Specify whether pages are marked as being inactive when they are freed. This is used in CMO environments diff --git a/arch/Kconfig b/arch/Kconfig index 684eb5af439d..0a3ffe46e567 100644 --- a/arch/Kconfig +++ b/arch/Kconfig @@ -142,6 +142,9 @@ config HAVE_ARCH_TRACEHOOK config HAVE_DMA_ATTRS bool +config HAVE_DMA_CONTIGUOUS + bool + config USE_GENERIC_SMP_HELPERS bool diff --git a/drivers/base/Kconfig b/drivers/base/Kconfig index 9aa618acfe97..9b21469482ae 100644 --- a/drivers/base/Kconfig +++ b/drivers/base/Kconfig @@ -192,4 +192,93 @@ config DMA_SHARED_BUFFER APIs extension; the file's descriptor can then be passed on to other driver. +config CMA + bool "Contiguous Memory Allocator (EXPERIMENTAL)" + depends on HAVE_DMA_CONTIGUOUS && HAVE_MEMBLOCK && EXPERIMENTAL + select MIGRATION + help + This enables the Contiguous Memory Allocator which allows drivers + to allocate big physically-contiguous blocks of memory for use with + hardware components that do not support I/O map nor scatter-gather. + + For more information see . + If unsure, say "n". + +if CMA + +config CMA_DEBUG + bool "CMA debug messages (DEVELOPMENT)" + depends on DEBUG_KERNEL + help + Turns on debug messages in CMA. This produces KERN_DEBUG + messages for every CMA call as well as various messages while + processing calls such as dma_alloc_from_contiguous(). + This option does not affect warning and error messages. + +comment "Default contiguous memory area size:" + +config CMA_SIZE_MBYTES + int "Size in Mega Bytes" + depends on !CMA_SIZE_SEL_PERCENTAGE + default 16 + help + Defines the size (in MiB) of the default memory area for Contiguous + Memory Allocator. + +config CMA_SIZE_PERCENTAGE + int "Percentage of total memory" + depends on !CMA_SIZE_SEL_MBYTES + default 10 + help + Defines the size of the default memory area for Contiguous Memory + Allocator as a percentage of the total memory in the system. + +choice + prompt "Selected region size" + default CMA_SIZE_SEL_ABSOLUTE + +config CMA_SIZE_SEL_MBYTES + bool "Use mega bytes value only" + +config CMA_SIZE_SEL_PERCENTAGE + bool "Use percentage value only" + +config CMA_SIZE_SEL_MIN + bool "Use lower value (minimum)" + +config CMA_SIZE_SEL_MAX + bool "Use higher value (maximum)" + +endchoice + +config CMA_ALIGNMENT + int "Maximum PAGE_SIZE order of alignment for contiguous buffers" + range 4 9 + default 8 + help + DMA mapping framework by default aligns all buffers to the smallest + PAGE_SIZE order which is greater than or equal to the requested buffer + size. This works well for buffers up to a few hundreds kilobytes, but + for larger buffers it just a memory waste. With this parameter you can + specify the maximum PAGE_SIZE order for contiguous buffers. Larger + buffers will be aligned only to this specified order. The order is + expressed as a power of two multiplied by the PAGE_SIZE. + + For example, if your system defaults to 4KiB pages, the order value + of 8 means that the buffers will be aligned up to 1MiB only. + + If unsure, leave the default value "8". + +config CMA_AREAS + int "Maximum count of the CMA device-private areas" + default 7 + help + CMA allows to create CMA areas for particular devices. This parameter + sets the maximum number of such device private CMA areas in the + system. + + If unsure, leave the default value "7". + +endif + endmenu diff --git a/drivers/base/Makefile b/drivers/base/Makefile index b6d1b9c4200c..5aa2d703d19f 100644 --- a/drivers/base/Makefile +++ b/drivers/base/Makefile @@ -6,6 +6,7 @@ obj-y := core.o bus.o dd.o syscore.o \ attribute_container.o transport_class.o \ topology.o obj-$(CONFIG_DEVTMPFS) += devtmpfs.o +obj-$(CONFIG_CMA) += dma-contiguous.o obj-y += power/ obj-$(CONFIG_HAS_DMA) += dma-mapping.o obj-$(CONFIG_HAVE_GENERIC_DMA_COHERENT) += dma-coherent.o diff --git a/drivers/base/dma-contiguous.c b/drivers/base/dma-contiguous.c new file mode 100644 index 000000000000..78efb0306a44 --- /dev/null +++ b/drivers/base/dma-contiguous.c @@ -0,0 +1,401 @@ +/* + * Contiguous Memory Allocator for DMA mapping framework + * Copyright (c) 2010-2011 by Samsung Electronics. + * Written by: + * Marek Szyprowski + * Michal Nazarewicz + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation; either version 2 of the + * License or (at your optional) any later version of the license. + */ + +#define pr_fmt(fmt) "cma: " fmt + +#ifdef CONFIG_CMA_DEBUG +#ifndef DEBUG +# define DEBUG +#endif +#endif + +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#ifndef SZ_1M +#define SZ_1M (1 << 20) +#endif + +struct cma { + unsigned long base_pfn; + unsigned long count; + unsigned long *bitmap; +}; + +struct cma *dma_contiguous_default_area; + +#ifdef CONFIG_CMA_SIZE_MBYTES +#define CMA_SIZE_MBYTES CONFIG_CMA_SIZE_MBYTES +#else +#define CMA_SIZE_MBYTES 0 +#endif + +/* + * Default global CMA area size can be defined in kernel's .config. + * This is usefull mainly for distro maintainers to create a kernel + * that works correctly for most supported systems. + * The size can be set in bytes or as a percentage of the total memory + * in the system. + * + * Users, who want to set the size of global CMA area for their system + * should use cma= kernel parameter. + */ +static const unsigned long size_bytes = CMA_SIZE_MBYTES * SZ_1M; +static long size_cmdline = -1; + +static int __init early_cma(char *p) +{ + pr_debug("%s(%s)\n", __func__, p); + size_cmdline = memparse(p, &p); + return 0; +} +early_param("cma", early_cma); + +#ifdef CONFIG_CMA_SIZE_PERCENTAGE + +static unsigned long __init __maybe_unused cma_early_percent_memory(void) +{ + struct memblock_region *reg; + unsigned long total_pages = 0; + + /* + * We cannot use memblock_phys_mem_size() here, because + * memblock_analyze() has not been called yet. + */ + for_each_memblock(memory, reg) + total_pages += memblock_region_memory_end_pfn(reg) - + memblock_region_memory_base_pfn(reg); + + return (total_pages * CONFIG_CMA_SIZE_PERCENTAGE / 100) << PAGE_SHIFT; +} + +#else + +static inline __maybe_unused unsigned long cma_early_percent_memory(void) +{ + return 0; +} + +#endif + +/** + * dma_contiguous_reserve() - reserve area for contiguous memory handling + * @limit: End address of the reserved memory (optional, 0 for any). + * + * This function reserves memory from early allocator. It should be + * called by arch specific code once the early allocator (memblock or bootmem) + * has been activated and all other subsystems have already allocated/reserved + * memory. + */ +void __init dma_contiguous_reserve(phys_addr_t limit) +{ + unsigned long selected_size = 0; + + pr_debug("%s(limit %08lx)\n", __func__, (unsigned long)limit); + + if (size_cmdline != -1) { + selected_size = size_cmdline; + } else { +#ifdef CONFIG_CMA_SIZE_SEL_MBYTES + selected_size = size_bytes; +#elif defined(CONFIG_CMA_SIZE_SEL_PERCENTAGE) + selected_size = cma_early_percent_memory(); +#elif defined(CONFIG_CMA_SIZE_SEL_MIN) + selected_size = min(size_bytes, cma_early_percent_memory()); +#elif defined(CONFIG_CMA_SIZE_SEL_MAX) + selected_size = max(size_bytes, cma_early_percent_memory()); +#endif + } + + if (selected_size) { + pr_debug("%s: reserving %ld MiB for global area\n", __func__, + selected_size / SZ_1M); + + dma_declare_contiguous(NULL, selected_size, 0, limit); + } +}; + +static DEFINE_MUTEX(cma_mutex); + +static __init int cma_activate_area(unsigned long base_pfn, unsigned long count) +{ + unsigned long pfn = base_pfn; + unsigned i = count >> pageblock_order; + struct zone *zone; + + WARN_ON_ONCE(!pfn_valid(pfn)); + zone = page_zone(pfn_to_page(pfn)); + + do { + unsigned j; + base_pfn = pfn; + for (j = pageblock_nr_pages; j; --j, pfn++) { + WARN_ON_ONCE(!pfn_valid(pfn)); + if (page_zone(pfn_to_page(pfn)) != zone) + return -EINVAL; + } + init_cma_reserved_pageblock(pfn_to_page(base_pfn)); + } while (--i); + return 0; +} + +static __init struct cma *cma_create_area(unsigned long base_pfn, + unsigned long count) +{ + int bitmap_size = BITS_TO_LONGS(count) * sizeof(long); + struct cma *cma; + int ret = -ENOMEM; + + pr_debug("%s(base %08lx, count %lx)\n", __func__, base_pfn, count); + + cma = kmalloc(sizeof *cma, GFP_KERNEL); + if (!cma) + return ERR_PTR(-ENOMEM); + + cma->base_pfn = base_pfn; + cma->count = count; + cma->bitmap = kzalloc(bitmap_size, GFP_KERNEL); + + if (!cma->bitmap) + goto no_mem; + + ret = cma_activate_area(base_pfn, count); + if (ret) + goto error; + + pr_debug("%s: returned %p\n", __func__, (void *)cma); + return cma; + +error: + kfree(cma->bitmap); +no_mem: + kfree(cma); + return ERR_PTR(ret); +} + +static struct cma_reserved { + phys_addr_t start; + unsigned long size; + struct device *dev; +} cma_reserved[MAX_CMA_AREAS] __initdata; +static unsigned cma_reserved_count __initdata; + +static int __init cma_init_reserved_areas(void) +{ + struct cma_reserved *r = cma_reserved; + unsigned i = cma_reserved_count; + + pr_debug("%s()\n", __func__); + + for (; i; --i, ++r) { + struct cma *cma; + cma = cma_create_area(PFN_DOWN(r->start), + r->size >> PAGE_SHIFT); + if (!IS_ERR(cma)) + dev_set_cma_area(r->dev, cma); + } + return 0; +} +core_initcall(cma_init_reserved_areas); + +/** + * dma_declare_contiguous() - reserve area for contiguous memory handling + * for particular device + * @dev: Pointer to device structure. + * @size: Size of the reserved memory. + * @base: Start address of the reserved memory (optional, 0 for any). + * @limit: End address of the reserved memory (optional, 0 for any). + * + * This function reserves memory for specified device. It should be + * called by board specific code when early allocator (memblock or bootmem) + * is still activate. + */ +int __init dma_declare_contiguous(struct device *dev, unsigned long size, + phys_addr_t base, phys_addr_t limit) +{ + struct cma_reserved *r = &cma_reserved[cma_reserved_count]; + unsigned long alignment; + + pr_debug("%s(size %lx, base %08lx, limit %08lx)\n", __func__, + (unsigned long)size, (unsigned long)base, + (unsigned long)limit); + + /* Sanity checks */ + if (cma_reserved_count == ARRAY_SIZE(cma_reserved)) { + pr_err("Not enough slots for CMA reserved regions!\n"); + return -ENOSPC; + } + + if (!size) + return -EINVAL; + + /* Sanitise input arguments */ + alignment = PAGE_SIZE << max(MAX_ORDER, pageblock_order); + base = ALIGN(base, alignment); + size = ALIGN(size, alignment); + limit &= ~(alignment - 1); + + /* Reserve memory */ + if (base) { + if (memblock_is_region_reserved(base, size) || + memblock_reserve(base, size) < 0) { + base = -EBUSY; + goto err; + } + } else { + /* + * Use __memblock_alloc_base() since + * memblock_alloc_base() panic()s. + */ + phys_addr_t addr = __memblock_alloc_base(size, alignment, limit); + if (!addr) { + base = -ENOMEM; + goto err; + } else if (addr + size > ~(unsigned long)0) { + memblock_free(addr, size); + base = -EINVAL; + goto err; + } else { + base = addr; + } + } + + /* + * Each reserved area must be initialised later, when more kernel + * subsystems (like slab allocator) are available. + */ + r->start = base; + r->size = size; + r->dev = dev; + cma_reserved_count++; + pr_info("CMA: reserved %ld MiB at %08lx\n", size / SZ_1M, + (unsigned long)base); + + /* Architecture specific contiguous memory fixup. */ + dma_contiguous_early_fixup(base, size); + return 0; +err: + pr_err("CMA: failed to reserve %ld MiB\n", size / SZ_1M); + return base; +} + +/** + * dma_alloc_from_contiguous() - allocate pages from contiguous area + * @dev: Pointer to device for which the allocation is performed. + * @count: Requested number of pages. + * @align: Requested alignment of pages (in PAGE_SIZE order). + * + * This function allocates memory buffer for specified device. It uses + * device specific contiguous memory area if available or the default + * global one. Requires architecture specific get_dev_cma_area() helper + * function. + */ +struct page *dma_alloc_from_contiguous(struct device *dev, int count, + unsigned int align) +{ + unsigned long mask, pfn, pageno, start = 0; + struct cma *cma = dev_get_cma_area(dev); + int ret; + + if (!cma || !cma->count) + return NULL; + + if (align > CONFIG_CMA_ALIGNMENT) + align = CONFIG_CMA_ALIGNMENT; + + pr_debug("%s(cma %p, count %d, align %d)\n", __func__, (void *)cma, + count, align); + + if (!count) + return NULL; + + mask = (1 << align) - 1; + + mutex_lock(&cma_mutex); + + for (;;) { + pageno = bitmap_find_next_zero_area(cma->bitmap, cma->count, + start, count, mask); + if (pageno >= cma->count) { + ret = -ENOMEM; + goto error; + } + + pfn = cma->base_pfn + pageno; + ret = alloc_contig_range(pfn, pfn + count, MIGRATE_CMA); + if (ret == 0) { + bitmap_set(cma->bitmap, pageno, count); + break; + } else if (ret != -EBUSY) { + goto error; + } + pr_debug("%s(): memory range at %p is busy, retrying\n", + __func__, pfn_to_page(pfn)); + /* try again with a bit different memory target */ + start = pageno + mask + 1; + } + + mutex_unlock(&cma_mutex); + + pr_debug("%s(): returned %p\n", __func__, pfn_to_page(pfn)); + return pfn_to_page(pfn); +error: + mutex_unlock(&cma_mutex); + return NULL; +} + +/** + * dma_release_from_contiguous() - release allocated pages + * @dev: Pointer to device for which the pages were allocated. + * @pages: Allocated pages. + * @count: Number of allocated pages. + * + * This function releases memory allocated by dma_alloc_from_contiguous(). + * It returns false when provided pages do not belong to contiguous area and + * true otherwise. + */ +bool dma_release_from_contiguous(struct device *dev, struct page *pages, + int count) +{ + struct cma *cma = dev_get_cma_area(dev); + unsigned long pfn; + + if (!cma || !pages) + return false; + + pr_debug("%s(page %p)\n", __func__, (void *)pages); + + pfn = page_to_pfn(pages); + + if (pfn < cma->base_pfn || pfn >= cma->base_pfn + cma->count) + return false; + + VM_BUG_ON(pfn + count > cma->base_pfn + cma->count); + + mutex_lock(&cma_mutex); + bitmap_clear(cma->bitmap, pfn - cma->base_pfn, count); + free_contig_range(pfn, count); + mutex_unlock(&cma_mutex); + + return true; +} diff --git a/include/asm-generic/dma-contiguous.h b/include/asm-generic/dma-contiguous.h new file mode 100644 index 000000000000..c544356b374b --- /dev/null +++ b/include/asm-generic/dma-contiguous.h @@ -0,0 +1,28 @@ +#ifndef ASM_DMA_CONTIGUOUS_H +#define ASM_DMA_CONTIGUOUS_H + +#ifdef __KERNEL__ +#ifdef CONFIG_CMA + +#include +#include + +static inline struct cma *dev_get_cma_area(struct device *dev) +{ + if (dev && dev->cma_area) + return dev->cma_area; + return dma_contiguous_default_area; +} + +static inline void dev_set_cma_area(struct device *dev, struct cma *cma) +{ + if (dev) + dev->cma_area = cma; + if (!dev || !dma_contiguous_default_area) + dma_contiguous_default_area = cma; +} + +#endif +#endif + +#endif diff --git a/include/linux/device.h b/include/linux/device.h index 5ad17cccdd71..e3399290436e 100644 --- a/include/linux/device.h +++ b/include/linux/device.h @@ -661,6 +661,10 @@ struct device { struct dma_coherent_mem *dma_mem; /* internal for coherent mem override */ +#ifdef CONFIG_CMA + struct cma *cma_area; /* contiguous memory area for dma + allocations */ +#endif /* arch specific additions */ struct dev_archdata archdata; diff --git a/include/linux/dma-contiguous.h b/include/linux/dma-contiguous.h new file mode 100644 index 000000000000..2f303e4b7ed3 --- /dev/null +++ b/include/linux/dma-contiguous.h @@ -0,0 +1,110 @@ +#ifndef __LINUX_CMA_H +#define __LINUX_CMA_H + +/* + * Contiguous Memory Allocator for DMA mapping framework + * Copyright (c) 2010-2011 by Samsung Electronics. + * Written by: + * Marek Szyprowski + * Michal Nazarewicz + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation; either version 2 of the + * License or (at your optional) any later version of the license. + */ + +/* + * Contiguous Memory Allocator + * + * The Contiguous Memory Allocator (CMA) makes it possible to + * allocate big contiguous chunks of memory after the system has + * booted. + * + * Why is it needed? + * + * Various devices on embedded systems have no scatter-getter and/or + * IO map support and require contiguous blocks of memory to + * operate. They include devices such as cameras, hardware video + * coders, etc. + * + * Such devices often require big memory buffers (a full HD frame + * is, for instance, more then 2 mega pixels large, i.e. more than 6 + * MB of memory), which makes mechanisms such as kmalloc() or + * alloc_page() ineffective. + * + * At the same time, a solution where a big memory region is + * reserved for a device is suboptimal since often more memory is + * reserved then strictly required and, moreover, the memory is + * inaccessible to page system even if device drivers don't use it. + * + * CMA tries to solve this issue by operating on memory regions + * where only movable pages can be allocated from. This way, kernel + * can use the memory for pagecache and when device driver requests + * it, allocated pages can be migrated. + * + * Driver usage + * + * CMA should not be used by the device drivers directly. It is + * only a helper framework for dma-mapping subsystem. + * + * For more information, see kernel-docs in drivers/base/dma-contiguous.c + */ + +#ifdef __KERNEL__ + +struct cma; +struct page; +struct device; + +#ifdef CONFIG_CMA + +/* + * There is always at least global CMA area and a few optional device + * private areas configured in kernel .config. + */ +#define MAX_CMA_AREAS (1 + CONFIG_CMA_AREAS) + +extern struct cma *dma_contiguous_default_area; + +void dma_contiguous_reserve(phys_addr_t addr_limit); +int dma_declare_contiguous(struct device *dev, unsigned long size, + phys_addr_t base, phys_addr_t limit); + +struct page *dma_alloc_from_contiguous(struct device *dev, int count, + unsigned int order); +bool dma_release_from_contiguous(struct device *dev, struct page *pages, + int count); + +#else + +#define MAX_CMA_AREAS (0) + +static inline void dma_contiguous_reserve(phys_addr_t limit) { } + +static inline +int dma_declare_contiguous(struct device *dev, unsigned long size, + phys_addr_t base, phys_addr_t limit) +{ + return -ENOSYS; +} + +static inline +struct page *dma_alloc_from_contiguous(struct device *dev, int count, + unsigned int order) +{ + return NULL; +} + +static inline +bool dma_release_from_contiguous(struct device *dev, struct page *pages, + int count) +{ + return false; +} + +#endif + +#endif + +#endif -- cgit v1.2.3-70-g09d2 From 322728e55aa7834e2fab2786b76df183c4843a12 Mon Sep 17 00:00:00 2001 From: Paul Gortmaker Date: Fri, 18 May 2012 13:59:39 -0400 Subject: KVM: make asm-generic/kvm_para.h have an ifdef __KERNEL__ block There are two functions in this asm-generic file. Looking at other arch which do not use the generic version, these two fcns are within an #ifdef __KERNEL__ block, so make the generic one consistent with those. Signed-off-by: Paul Gortmaker Signed-off-by: Avi Kivity --- include/asm-generic/kvm_para.h | 3 +++ 1 file changed, 3 insertions(+) (limited to 'include/asm-generic') diff --git a/include/asm-generic/kvm_para.h b/include/asm-generic/kvm_para.h index 9a7bbadb688d..5cba37f9eae1 100644 --- a/include/asm-generic/kvm_para.h +++ b/include/asm-generic/kvm_para.h @@ -1,6 +1,7 @@ #ifndef _ASM_GENERIC_KVM_PARA_H #define _ASM_GENERIC_KVM_PARA_H +#ifdef __KERNEL__ /* * This function is used by architectures that support kvm to avoid issuing @@ -16,4 +17,6 @@ static inline unsigned int kvm_arch_para_features(void) return 0; } +#endif /* _KERNEL__ */ + #endif -- cgit v1.2.3-70-g09d2 From 73636b1aacb1a07e6fbe0d25e560e69b024a8e25 Mon Sep 17 00:00:00 2001 From: Chris Metcalf Date: Wed, 28 Mar 2012 13:59:18 -0400 Subject: arch/tile: allow building Linux with transparent huge pages enabled The change adds some infrastructure for managing tile pmd's more generally, using pte_pmd() and pmd_pte() methods to translate pmd values to and from ptes, since on TILEPro a pmd is really just a nested structure holding a pgd (aka pte). Several existing pmd methods are moved into this framework, and a whole raft of additional pmd accessors are defined that are used by the transparent hugepage framework. The tile PTE now has a "client2" bit. The bit is used to indicate a transparent huge page is in the process of being split into subpages. This change also fixes a generic bug where the return value of the generic pmdp_splitting_flush() was incorrect. Signed-off-by: Chris Metcalf --- arch/tile/include/asm/pgtable.h | 89 +++++++++++++++++++++++++++++++++++--- arch/tile/include/asm/pgtable_32.h | 26 ++++------- arch/tile/include/asm/pgtable_64.h | 29 +++---------- arch/tile/include/hv/hypervisor.h | 11 ++++- include/asm-generic/pgtable.h | 5 +-- mm/pgtable-generic.c | 4 +- 6 files changed, 111 insertions(+), 53 deletions(-) (limited to 'include/asm-generic') diff --git a/arch/tile/include/asm/pgtable.h b/arch/tile/include/asm/pgtable.h index 67490910774d..ec907d4dbd7a 100644 --- a/arch/tile/include/asm/pgtable.h +++ b/arch/tile/include/asm/pgtable.h @@ -187,6 +187,7 @@ static inline void __pte_clear(pte_t *ptep) * Undefined behaviour if not.. */ #define pte_present hv_pte_get_present +#define pte_mknotpresent hv_pte_clear_present #define pte_user hv_pte_get_user #define pte_read hv_pte_get_readable #define pte_dirty hv_pte_get_dirty @@ -312,7 +313,7 @@ extern void check_mm_caching(struct mm_struct *prev, struct mm_struct *next); */ static inline pte_t pte_modify(pte_t pte, pgprot_t newprot) { - return pfn_pte(hv_pte_get_pfn(pte), newprot); + return pfn_pte(pte_pfn(pte), newprot); } /* @@ -410,6 +411,46 @@ static inline unsigned long pmd_index(unsigned long address) return (address >> PMD_SHIFT) & (PTRS_PER_PMD - 1); } +#define __HAVE_ARCH_PMDP_TEST_AND_CLEAR_YOUNG +static inline int pmdp_test_and_clear_young(struct vm_area_struct *vma, + unsigned long address, + pmd_t *pmdp) +{ + return ptep_test_and_clear_young(vma, address, pmdp_ptep(pmdp)); +} + +#define __HAVE_ARCH_PMDP_SET_WRPROTECT +static inline void pmdp_set_wrprotect(struct mm_struct *mm, + unsigned long address, pmd_t *pmdp) +{ + ptep_set_wrprotect(mm, address, pmdp_ptep(pmdp)); +} + + +#define __HAVE_ARCH_PMDP_GET_AND_CLEAR +static inline pmd_t pmdp_get_and_clear(struct mm_struct *mm, + unsigned long address, + pmd_t *pmdp) +{ + return pte_pmd(ptep_get_and_clear(mm, address, pmdp_ptep(pmdp))); +} + +static inline void __set_pmd(pmd_t *pmdp, pmd_t pmdval) +{ + set_pte(pmdp_ptep(pmdp), pmd_pte(pmdval)); +} + +#define set_pmd_at(mm, addr, pmdp, pmdval) __set_pmd(pmdp, pmdval) + +/* Create a pmd from a PTFN. */ +static inline pmd_t ptfn_pmd(unsigned long ptfn, pgprot_t prot) +{ + return pte_pmd(hv_pte_set_ptfn(prot, ptfn)); +} + +/* Return the page-table frame number (ptfn) that a pmd_t points at. */ +#define pmd_ptfn(pmd) hv_pte_get_ptfn(pmd_pte(pmd)) + /* * A given kernel pmd_t maps to a specific virtual address (either a * kernel huge page or a kernel pte_t table). Since kernel pte_t @@ -432,6 +473,47 @@ static inline unsigned long pmd_page_vaddr(pmd_t pmd) */ #define pmd_page(pmd) pfn_to_page(HV_PTFN_TO_PFN(pmd_ptfn(pmd))) +static inline void pmd_clear(pmd_t *pmdp) +{ + __pte_clear(pmdp_ptep(pmdp)); +} + +#define pmd_mknotpresent(pmd) pte_pmd(pte_mknotpresent(pmd_pte(pmd))) +#define pmd_young(pmd) pte_young(pmd_pte(pmd)) +#define pmd_mkyoung(pmd) pte_pmd(pte_mkyoung(pmd_pte(pmd))) +#define pmd_mkold(pmd) pte_pmd(pte_mkold(pmd_pte(pmd))) +#define pmd_mkwrite(pmd) pte_pmd(pte_mkwrite(pmd_pte(pmd))) +#define pmd_write(pmd) pte_write(pmd_pte(pmd)) +#define pmd_wrprotect(pmd) pte_pmd(pte_wrprotect(pmd_pte(pmd))) +#define pmd_mkdirty(pmd) pte_pmd(pte_mkdirty(pmd_pte(pmd))) +#define pmd_huge_page(pmd) pte_huge(pmd_pte(pmd)) +#define pmd_mkhuge(pmd) pte_pmd(pte_mkhuge(pmd_pte(pmd))) +#define __HAVE_ARCH_PMD_WRITE + +#define pfn_pmd(pfn, pgprot) pte_pmd(pfn_pte((pfn), (pgprot))) +#define pmd_pfn(pmd) pte_pfn(pmd_pte(pmd)) +#define mk_pmd(page, pgprot) pfn_pmd(page_to_pfn(page), (pgprot)) + +static inline pmd_t pmd_modify(pmd_t pmd, pgprot_t newprot) +{ + return pfn_pmd(pmd_pfn(pmd), newprot); +} + +#ifdef CONFIG_TRANSPARENT_HUGEPAGE +#define has_transparent_hugepage() 1 +#define pmd_trans_huge pmd_huge_page + +static inline pmd_t pmd_mksplitting(pmd_t pmd) +{ + return pte_pmd(hv_pte_set_client2(pmd_pte(pmd))); +} + +static inline int pmd_trans_splitting(pmd_t pmd) +{ + return hv_pte_get_client2(pmd_pte(pmd)); +} +#endif /* CONFIG_TRANSPARENT_HUGEPAGE */ + /* * The pte page can be thought of an array like this: pte_t[PTRS_PER_PTE] * @@ -448,11 +530,6 @@ static inline pte_t *pte_offset_kernel(pmd_t *pmd, unsigned long address) return (pte_t *)pmd_page_vaddr(*pmd) + pte_index(address); } -static inline int pmd_huge_page(pmd_t pmd) -{ - return pmd_val(pmd) & _PAGE_HUGE_PAGE; -} - #include /* Support /proc/NN/pgtable API. */ diff --git a/arch/tile/include/asm/pgtable_32.h b/arch/tile/include/asm/pgtable_32.h index 9f98529761fd..27e20f6844a8 100644 --- a/arch/tile/include/asm/pgtable_32.h +++ b/arch/tile/include/asm/pgtable_32.h @@ -111,24 +111,14 @@ static inline pte_t ptep_get_and_clear(struct mm_struct *mm, return pte; } -static inline void __set_pmd(pmd_t *pmdp, pmd_t pmdval) -{ - set_pte(&pmdp->pud.pgd, pmdval.pud.pgd); -} - -/* Create a pmd from a PTFN. */ -static inline pmd_t ptfn_pmd(unsigned long ptfn, pgprot_t prot) -{ - return (pmd_t){ { hv_pte_set_ptfn(prot, ptfn) } }; -} - -/* Return the page-table frame number (ptfn) that a pmd_t points at. */ -#define pmd_ptfn(pmd) hv_pte_get_ptfn((pmd).pud.pgd) - -static inline void pmd_clear(pmd_t *pmdp) -{ - __pte_clear(&pmdp->pud.pgd); -} +/* + * pmds are wrappers around pgds, which are the same as ptes. + * It's often convenient to "cast" back and forth and use the pte methods, + * which are the methods supplied by the hypervisor. + */ +#define pmd_pte(pmd) ((pmd).pud.pgd) +#define pmdp_ptep(pmdp) (&(pmdp)->pud.pgd) +#define pte_pmd(pte) ((pmd_t){ { (pte) } }) #endif /* __ASSEMBLY__ */ diff --git a/arch/tile/include/asm/pgtable_64.h b/arch/tile/include/asm/pgtable_64.h index fd80328523b4..e105f3ada655 100644 --- a/arch/tile/include/asm/pgtable_64.h +++ b/arch/tile/include/asm/pgtable_64.h @@ -108,28 +108,6 @@ static inline unsigned long pud_index(unsigned long address) #define pmd_offset(pud, address) \ ((pmd_t *)pud_page_vaddr(*(pud)) + pmd_index(address)) -static inline void __set_pmd(pmd_t *pmdp, pmd_t pmdval) -{ - set_pte(pmdp, pmdval); -} - -/* Create a pmd from a PTFN and pgprot. */ -static inline pmd_t ptfn_pmd(unsigned long ptfn, pgprot_t prot) -{ - return hv_pte_set_ptfn(prot, ptfn); -} - -/* Return the page-table frame number (ptfn) that a pmd_t points at. */ -static inline unsigned long pmd_ptfn(pmd_t pmd) -{ - return hv_pte_get_ptfn(pmd); -} - -static inline void pmd_clear(pmd_t *pmdp) -{ - __pte_clear(pmdp); -} - /* Normalize an address to having the correct high bits set. */ #define pgd_addr_normalize pgd_addr_normalize static inline unsigned long pgd_addr_normalize(unsigned long addr) @@ -170,6 +148,13 @@ static inline pte_t ptep_get_and_clear(struct mm_struct *mm, return hv_pte(__insn_exch(&ptep->val, 0UL)); } +/* + * pmds are the same as pgds and ptes, so converting is a no-op. + */ +#define pmd_pte(pmd) (pmd) +#define pmdp_ptep(pmdp) (pmdp) +#define pte_pmd(pte) (pte) + #endif /* __ASSEMBLY__ */ #endif /* _ASM_TILE_PGTABLE_64_H */ diff --git a/arch/tile/include/hv/hypervisor.h b/arch/tile/include/hv/hypervisor.h index 72ec1e972f15..793123e116fd 100644 --- a/arch/tile/include/hv/hypervisor.h +++ b/arch/tile/include/hv/hypervisor.h @@ -1855,8 +1855,7 @@ int hv_flush_remote(HV_PhysAddr cache_pa, unsigned long cache_control, future use. */ #define HV_PTE_INDEX_MODE 16 /**< Page mode; see HV_PTE_MODE_xxx */ #define HV_PTE_MODE_BITS 3 /**< Number of bits in mode */ - /* Bit 19 is reserved for - future use. */ +#define HV_PTE_INDEX_CLIENT2 19 /**< Page client state 2 */ #define HV_PTE_INDEX_LOTAR 20 /**< Page's LOTAR; must be high bits of word */ #define HV_PTE_LOTAR_BITS 12 /**< Number of bits in a LOTAR */ @@ -2046,6 +2045,13 @@ int hv_flush_remote(HV_PhysAddr cache_pa, unsigned long cache_control, */ #define HV_PTE_CLIENT1 (__HV_PTE_ONE << HV_PTE_INDEX_CLIENT1) +/** Client-private bit in PTE. + * + * This bit is guaranteed not to be inspected or modified by the + * hypervisor. + */ +#define HV_PTE_CLIENT2 (__HV_PTE_ONE << HV_PTE_INDEX_CLIENT2) + /** Non-coherent (NC) bit in PTE. * * If this bit is set, the mapping that is set up will be non-coherent @@ -2180,6 +2186,7 @@ _HV_BIT(present, PRESENT) _HV_BIT(page, PAGE) _HV_BIT(client0, CLIENT0) _HV_BIT(client1, CLIENT1) +_HV_BIT(client2, CLIENT2) _HV_BIT(migrating, MIGRATING) _HV_BIT(nc, NC) _HV_BIT(readable, READABLE) diff --git a/include/asm-generic/pgtable.h b/include/asm-generic/pgtable.h index 125c54e98517..e2768f188f55 100644 --- a/include/asm-generic/pgtable.h +++ b/include/asm-generic/pgtable.h @@ -158,9 +158,8 @@ static inline void pmdp_set_wrprotect(struct mm_struct *mm, #endif #ifndef __HAVE_ARCH_PMDP_SPLITTING_FLUSH -extern pmd_t pmdp_splitting_flush(struct vm_area_struct *vma, - unsigned long address, - pmd_t *pmdp); +extern void pmdp_splitting_flush(struct vm_area_struct *vma, + unsigned long address, pmd_t *pmdp); #endif #ifndef __HAVE_ARCH_PTE_SAME diff --git a/mm/pgtable-generic.c b/mm/pgtable-generic.c index 5a74fea182f1..74c0ddaa6fa0 100644 --- a/mm/pgtable-generic.c +++ b/mm/pgtable-generic.c @@ -109,8 +109,8 @@ pmd_t pmdp_clear_flush(struct vm_area_struct *vma, unsigned long address, #ifndef __HAVE_ARCH_PMDP_SPLITTING_FLUSH #ifdef CONFIG_TRANSPARENT_HUGEPAGE -pmd_t pmdp_splitting_flush(struct vm_area_struct *vma, unsigned long address, - pmd_t *pmdp) +void pmdp_splitting_flush(struct vm_area_struct *vma, unsigned long address, + pmd_t *pmdp) { pmd_t pmd = pmd_mksplitting(*pmdp); VM_BUG_ON(address & ~HPAGE_PMD_MASK); -- cgit v1.2.3-70-g09d2 From 36126f8f2ed8168eb13aa0662b9b9585cba100a9 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Sat, 26 May 2012 10:43:17 -0700 Subject: word-at-a-time: make the interfaces truly generic This changes the interfaces in to be a bit more complicated, but a lot more generic. In particular, it allows us to really do the operations efficiently on both little-endian and big-endian machines, pretty much regardless of machine details. For example, if you can rely on a fast population count instruction on your architecture, this will allow you to make your optimized file with that. NOTE! The "generic" version in include/asm-generic/word-at-a-time.h is not truly generic, it actually only works on big-endian. Why? Because on little-endian the generic algorithms are wasteful, since you can inevitably do better. The x86 implementation is an example of that. (The only truly non-generic part of the asm-generic implementation is the "find_zero()" function, and you could make a little-endian version of it. And if the Kbuild infrastructure allowed us to pick a particular header file, that would be lovely) The functions are as follows: - WORD_AT_A_TIME_CONSTANTS: specific constants that the algorithm uses. - has_zero(): take a word, and determine if it has a zero byte in it. It gets the word, the pointer to the constant pool, and a pointer to an intermediate "data" field it can set. This is the "quick-and-dirty" zero tester: it's what is run inside the hot loops. - "prep_zero_mask()": take the word, the data that has_zero() produced, and the constant pool, and generate an *exact* mask of which byte had the first zero. This is run directly *outside* the loop, and allows the "has_zero()" function to answer the "is there a zero byte" question without necessarily getting exactly *which* byte is the first one to contain a zero. If you do multiple byte lookups concurrently (eg "hash_name()", which looks for both NUL and '/' bytes), after you've done the prep_zero_mask() phase, the result of those can be or'ed together to get the "either or" case. - The result from "prep_zero_mask()" can then be fed into "find_zero()" (to find the byte offset of the first byte that was zero) or into "zero_bytemask()" (to find the bytemask of the bytes preceding the zero byte). The existence of zero_bytemask() is optional, and is not necessary for the normal string routines. But dentry name hashing needs it, so if you enable DENTRY_WORD_AT_A_TIME you need to expose it. This changes the generic strncpy_from_user() function and the dentry hashing functions to use these modified word-at-a-time interfaces. This gets us back to the optimized state of the x86 strncpy that we lost in the previous commit when moving over to the generic version. Signed-off-by: Linus Torvalds --- arch/openrisc/include/asm/Kbuild | 1 + arch/sparc/include/asm/Kbuild | 1 + arch/x86/include/asm/word-at-a-time.h | 32 +++++++++++++++++++-- fs/namei.c | 22 ++++++++------- include/asm-generic/word-at-a-time.h | 52 +++++++++++++++++++++++++++++++++++ lib/strncpy_from_user.c | 47 +++++-------------------------- 6 files changed, 102 insertions(+), 53 deletions(-) create mode 100644 include/asm-generic/word-at-a-time.h (limited to 'include/asm-generic') diff --git a/arch/openrisc/include/asm/Kbuild b/arch/openrisc/include/asm/Kbuild index c936483bc8e2..3f35c38d7b64 100644 --- a/arch/openrisc/include/asm/Kbuild +++ b/arch/openrisc/include/asm/Kbuild @@ -66,3 +66,4 @@ generic-y += topology.h generic-y += types.h generic-y += ucontext.h generic-y += user.h +generic-y += word-at-a-time.h diff --git a/arch/sparc/include/asm/Kbuild b/arch/sparc/include/asm/Kbuild index 2c2e38821f60..67f83e0a0d68 100644 --- a/arch/sparc/include/asm/Kbuild +++ b/arch/sparc/include/asm/Kbuild @@ -21,3 +21,4 @@ generic-y += div64.h generic-y += local64.h generic-y += irq_regs.h generic-y += local.h +generic-y += word-at-a-time.h diff --git a/arch/x86/include/asm/word-at-a-time.h b/arch/x86/include/asm/word-at-a-time.h index ae03facfadd6..5b238981542a 100644 --- a/arch/x86/include/asm/word-at-a-time.h +++ b/arch/x86/include/asm/word-at-a-time.h @@ -10,6 +10,11 @@ * bit count instruction, that might be better than the multiply * and shift, for example. */ +struct word_at_a_time { + const unsigned long one_bits, high_bits; +}; + +#define WORD_AT_A_TIME_CONSTANTS { REPEAT_BYTE(0x01), REPEAT_BYTE(0x80) } #ifdef CONFIG_64BIT @@ -37,10 +42,31 @@ static inline long count_masked_bytes(long mask) #endif -/* Return the high bit set in the first byte that is a zero */ -static inline unsigned long has_zero(unsigned long a) +/* Return nonzero if it has a zero */ +static inline unsigned long has_zero(unsigned long a, unsigned long *bits, const struct word_at_a_time *c) +{ + unsigned long mask = ((a - c->one_bits) & ~a) & c->high_bits; + *bits = mask; + return mask; +} + +static inline unsigned long prep_zero_mask(unsigned long a, unsigned long bits, const struct word_at_a_time *c) +{ + return bits; +} + +static inline unsigned long create_zero_mask(unsigned long bits) +{ + bits = (bits - 1) & ~bits; + return bits >> 7; +} + +/* The mask we created is directly usable as a bytemask */ +#define zero_bytemask(mask) (mask) + +static inline unsigned long find_zero(unsigned long mask) { - return ((a - REPEAT_BYTE(0x01)) & ~a) & REPEAT_BYTE(0x80); + return count_masked_bytes(mask); } /* diff --git a/fs/namei.c b/fs/namei.c index 93ff12b1a1de..c651f02c9fec 100644 --- a/fs/namei.c +++ b/fs/namei.c @@ -1452,7 +1452,8 @@ EXPORT_SYMBOL(full_name_hash); */ static inline unsigned long hash_name(const char *name, unsigned int *hashp) { - unsigned long a, mask, hash, len; + unsigned long a, b, adata, bdata, mask, hash, len; + const struct word_at_a_time constants = WORD_AT_A_TIME_CONSTANTS; hash = a = 0; len = -sizeof(unsigned long); @@ -1460,17 +1461,18 @@ static inline unsigned long hash_name(const char *name, unsigned int *hashp) hash = (hash + a) * 9; len += sizeof(unsigned long); a = load_unaligned_zeropad(name+len); - /* Do we have any NUL or '/' bytes in this word? */ - mask = has_zero(a) | has_zero(a ^ REPEAT_BYTE('/')); - } while (!mask); - - /* The mask *below* the first high bit set */ - mask = (mask - 1) & ~mask; - mask >>= 7; - hash += a & mask; + b = a ^ REPEAT_BYTE('/'); + } while (!(has_zero(a, &adata, &constants) | has_zero(b, &bdata, &constants))); + + adata = prep_zero_mask(a, adata, &constants); + bdata = prep_zero_mask(b, bdata, &constants); + + mask = create_zero_mask(adata | bdata); + + hash += a & zero_bytemask(mask); *hashp = fold_hash(hash); - return len + count_masked_bytes(mask); + return len + find_zero(mask); } #else diff --git a/include/asm-generic/word-at-a-time.h b/include/asm-generic/word-at-a-time.h new file mode 100644 index 000000000000..3f21f1b72e45 --- /dev/null +++ b/include/asm-generic/word-at-a-time.h @@ -0,0 +1,52 @@ +#ifndef _ASM_WORD_AT_A_TIME_H +#define _ASM_WORD_AT_A_TIME_H + +/* + * This says "generic", but it's actually big-endian only. + * Little-endian can use more efficient versions of these + * interfaces, see for example + * arch/x86/include/asm/word-at-a-time.h + * for those. + */ + +#include + +struct word_at_a_time { + const unsigned long high_bits, low_bits; +}; + +#define WORD_AT_A_TIME_CONSTANTS { REPEAT_BYTE(0xfe) + 1, REPEAT_BYTE(0x7f) } + +/* Bit set in the bytes that have a zero */ +static inline long prep_zero_mask(unsigned long val, unsigned long rhs, const struct word_at_a_time *c) +{ + unsigned long mask = (val & c->low_bits) + c->low_bits; + return ~(mask | rhs); +} + +#define create_zero_mask(mask) (mask) + +static inline long find_zero(unsigned long mask) +{ + long byte = 0; +#ifdef CONFIG_64BIT + if (mask >> 32) + mask >>= 32; + else + byte = 4; +#endif + if (mask >> 16) + mask >>= 16; + else + byte += 2; + return (mask >> 8) ? byte : byte + 1; +} + +static inline bool has_zero(unsigned long val, unsigned long *data, const struct word_at_a_time *c) +{ + unsigned long rhs = val | c->low_bits; + *data = rhs; + return (val + c->high_bits) & ~rhs; +} + +#endif /* _ASM_WORD_AT_A_TIME_H */ diff --git a/lib/strncpy_from_user.c b/lib/strncpy_from_user.c index c4c09b0e96ba..bb2b201d6ad0 100644 --- a/lib/strncpy_from_user.c +++ b/lib/strncpy_from_user.c @@ -4,37 +4,7 @@ #include #include - -static inline long find_zero(unsigned long mask) -{ - long byte = 0; - -#ifdef __BIG_ENDIAN -#ifdef CONFIG_64BIT - if (mask >> 32) - mask >>= 32; - else - byte = 4; -#endif - if (mask >> 16) - mask >>= 16; - else - byte += 2; - return (mask >> 8) ? byte : byte + 1; -#else -#ifdef CONFIG_64BIT - if (!((unsigned int) mask)) { - mask >>= 32; - byte = 4; - } -#endif - if (!(mask & 0xffff)) { - mask >>= 16; - byte += 2; - } - return (mask & 0xff) ? byte : byte + 1; -#endif -} +#include #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS #define IS_UNALIGNED(src, dst) 0 @@ -51,8 +21,7 @@ static inline long find_zero(unsigned long mask) */ static inline long do_strncpy_from_user(char *dst, const char __user *src, long count, unsigned long max) { - const unsigned long high_bits = REPEAT_BYTE(0xfe) + 1; - const unsigned long low_bits = REPEAT_BYTE(0x7f); + const struct word_at_a_time constants = WORD_AT_A_TIME_CONSTANTS; long res = 0; /* @@ -66,18 +35,16 @@ static inline long do_strncpy_from_user(char *dst, const char __user *src, long goto byte_at_a_time; while (max >= sizeof(unsigned long)) { - unsigned long c, v, rhs; + unsigned long c, data; /* Fall back to byte-at-a-time if we get a page fault */ if (unlikely(__get_user(c,(unsigned long __user *)(src+res)))) break; - rhs = c | low_bits; - v = (c + high_bits) & ~rhs; *(unsigned long *)(dst+res) = c; - if (v) { - v = (c & low_bits) + low_bits; - v = ~(v | rhs); - return res + find_zero(v); + if (has_zero(c, &data, &constants)) { + data = prep_zero_mask(c, data, &constants); + data = create_zero_mask(data); + return res + find_zero(data); } res += sizeof(unsigned long); max -= sizeof(unsigned long); -- cgit v1.2.3-70-g09d2 From 56457f38f212344fb38b250cfa7e7311c065022f Mon Sep 17 00:00:00 2001 From: Avi Kivity Date: Mon, 28 May 2012 17:35:22 +0300 Subject: KVM: Export asm-generic/kvm_para.h Prevents build failures on non-KVM archs. Tested-by: Geert Uytterhoeven Signed-off-by: Avi Kivity --- include/asm-generic/Kbuild | 1 + 1 file changed, 1 insertion(+) (limited to 'include/asm-generic') diff --git a/include/asm-generic/Kbuild b/include/asm-generic/Kbuild index 53f91b1ae53a..2c85a0f647b7 100644 --- a/include/asm-generic/Kbuild +++ b/include/asm-generic/Kbuild @@ -8,6 +8,7 @@ header-y += int-ll64.h header-y += ioctl.h header-y += ioctls.h header-y += ipcbuf.h +header-y += kvm_para.h header-y += mman-common.h header-y += mman.h header-y += msgbuf.h -- cgit v1.2.3-70-g09d2 From 26c191788f18129af0eb32a358cdaea0c7479626 Mon Sep 17 00:00:00 2001 From: Andrea Arcangeli Date: Tue, 29 May 2012 15:06:49 -0700 Subject: mm: pmd_read_atomic: fix 32bit PAE pmd walk vs pmd_populate SMP race condition When holding the mmap_sem for reading, pmd_offset_map_lock should only run on a pmd_t that has been read atomically from the pmdp pointer, otherwise we may read only half of it leading to this crash. PID: 11679 TASK: f06e8000 CPU: 3 COMMAND: "do_race_2_panic" #0 [f06a9dd8] crash_kexec at c049b5ec #1 [f06a9e2c] oops_end at c083d1c2 #2 [f06a9e40] no_context at c0433ded #3 [f06a9e64] bad_area_nosemaphore at c043401a #4 [f06a9e6c] __do_page_fault at c0434493 #5 [f06a9eec] do_page_fault at c083eb45 #6 [f06a9f04] error_code (via page_fault) at c083c5d5 EAX: 01fb470c EBX: fff35000 ECX: 00000003 EDX: 00000100 EBP: 00000000 DS: 007b ESI: 9e201000 ES: 007b EDI: 01fb4700 GS: 00e0 CS: 0060 EIP: c083bc14 ERR: ffffffff EFLAGS: 00010246 #7 [f06a9f38] _spin_lock at c083bc14 #8 [f06a9f44] sys_mincore at c0507b7d #9 [f06a9fb0] system_call at c083becd start len EAX: ffffffda EBX: 9e200000 ECX: 00001000 EDX: 6228537f DS: 007b ESI: 00000000 ES: 007b EDI: 003d0f00 SS: 007b ESP: 62285354 EBP: 62285388 GS: 0033 CS: 0073 EIP: 00291416 ERR: 000000da EFLAGS: 00000286 This should be a longstanding bug affecting x86 32bit PAE without THP. Only archs with 64bit large pmd_t and 32bit unsigned long should be affected. With THP enabled the barrier() in pmd_none_or_trans_huge_or_clear_bad() would partly hide the bug when the pmd transition from none to stable, by forcing a re-read of the *pmd in pmd_offset_map_lock, but when THP is enabled a new set of problem arises by the fact could then transition freely in any of the none, pmd_trans_huge or pmd_trans_stable states. So making the barrier in pmd_none_or_trans_huge_or_clear_bad() unconditional isn't good idea and it would be a flakey solution. This should be fully fixed by introducing a pmd_read_atomic that reads the pmd in order with THP disabled, or by reading the pmd atomically with cmpxchg8b with THP enabled. Luckily this new race condition only triggers in the places that must already be covered by pmd_none_or_trans_huge_or_clear_bad() so the fix is localized there but this bug is not related to THP. NOTE: this can trigger on x86 32bit systems with PAE enabled with more than 4G of ram, otherwise the high part of the pmd will never risk to be truncated because it would be zero at all times, in turn so hiding the SMP race. This bug was discovered and fully debugged by Ulrich, quote: ---- [..] pmd_none_or_trans_huge_or_clear_bad() loads the content of edx and eax. 496 static inline int pmd_none_or_trans_huge_or_clear_bad(pmd_t *pmd) 497 { 498 /* depend on compiler for an atomic pmd read */ 499 pmd_t pmdval = *pmd; // edi = pmd pointer 0xc0507a74 : mov 0x8(%esp),%edi ... // edx = PTE page table high address 0xc0507a84 : mov 0x4(%edi),%edx ... // eax = PTE page table low address 0xc0507a8e : mov (%edi),%eax [..] Please note that the PMD is not read atomically. These are two "mov" instructions where the high order bits of the PMD entry are fetched first. Hence, the above machine code is prone to the following race. - The PMD entry {high|low} is 0x0000000000000000. The "mov" at 0xc0507a84 loads 0x00000000 into edx. - A page fault (on another CPU) sneaks in between the two "mov" instructions and instantiates the PMD. - The PMD entry {high|low} is now 0x00000003fda38067. The "mov" at 0xc0507a8e loads 0xfda38067 into eax. ---- Reported-by: Ulrich Obergfell Signed-off-by: Andrea Arcangeli Cc: Mel Gorman Cc: Hugh Dickins Cc: Larry Woodman Cc: Petr Matousek Cc: Rik van Riel Cc: Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- arch/x86/include/asm/pgtable-3level.h | 50 +++++++++++++++++++++++++++++++++++ include/asm-generic/pgtable.h | 22 +++++++++++++-- 2 files changed, 70 insertions(+), 2 deletions(-) (limited to 'include/asm-generic') diff --git a/arch/x86/include/asm/pgtable-3level.h b/arch/x86/include/asm/pgtable-3level.h index effff47a3c82..43876f16caf1 100644 --- a/arch/x86/include/asm/pgtable-3level.h +++ b/arch/x86/include/asm/pgtable-3level.h @@ -31,6 +31,56 @@ static inline void native_set_pte(pte_t *ptep, pte_t pte) ptep->pte_low = pte.pte_low; } +#define pmd_read_atomic pmd_read_atomic +/* + * pte_offset_map_lock on 32bit PAE kernels was reading the pmd_t with + * a "*pmdp" dereference done by gcc. Problem is, in certain places + * where pte_offset_map_lock is called, concurrent page faults are + * allowed, if the mmap_sem is hold for reading. An example is mincore + * vs page faults vs MADV_DONTNEED. On the page fault side + * pmd_populate rightfully does a set_64bit, but if we're reading the + * pmd_t with a "*pmdp" on the mincore side, a SMP race can happen + * because gcc will not read the 64bit of the pmd atomically. To fix + * this all places running pmd_offset_map_lock() while holding the + * mmap_sem in read mode, shall read the pmdp pointer using this + * function to know if the pmd is null nor not, and in turn to know if + * they can run pmd_offset_map_lock or pmd_trans_huge or other pmd + * operations. + * + * Without THP if the mmap_sem is hold for reading, the + * pmd can only transition from null to not null while pmd_read_atomic runs. + * So there's no need of literally reading it atomically. + * + * With THP if the mmap_sem is hold for reading, the pmd can become + * THP or null or point to a pte (and in turn become "stable") at any + * time under pmd_read_atomic, so it's mandatory to read it atomically + * with cmpxchg8b. + */ +#ifndef CONFIG_TRANSPARENT_HUGEPAGE +static inline pmd_t pmd_read_atomic(pmd_t *pmdp) +{ + pmdval_t ret; + u32 *tmp = (u32 *)pmdp; + + ret = (pmdval_t) (*tmp); + if (ret) { + /* + * If the low part is null, we must not read the high part + * or we can end up with a partial pmd. + */ + smp_rmb(); + ret |= ((pmdval_t)*(tmp + 1)) << 32; + } + + return (pmd_t) { ret }; +} +#else /* CONFIG_TRANSPARENT_HUGEPAGE */ +static inline pmd_t pmd_read_atomic(pmd_t *pmdp) +{ + return (pmd_t) { atomic64_read((atomic64_t *)pmdp) }; +} +#endif /* CONFIG_TRANSPARENT_HUGEPAGE */ + static inline void native_set_pte_atomic(pte_t *ptep, pte_t pte) { set_64bit((unsigned long long *)(ptep), native_pte_val(pte)); diff --git a/include/asm-generic/pgtable.h b/include/asm-generic/pgtable.h index e2768f188f55..6f2b45a9b6bc 100644 --- a/include/asm-generic/pgtable.h +++ b/include/asm-generic/pgtable.h @@ -445,6 +445,18 @@ static inline int pmd_write(pmd_t pmd) #endif /* __HAVE_ARCH_PMD_WRITE */ #endif /* CONFIG_TRANSPARENT_HUGEPAGE */ +#ifndef pmd_read_atomic +static inline pmd_t pmd_read_atomic(pmd_t *pmdp) +{ + /* + * Depend on compiler for an atomic pmd read. NOTE: this is + * only going to work, if the pmdval_t isn't larger than + * an unsigned long. + */ + return *pmdp; +} +#endif + /* * This function is meant to be used by sites walking pagetables with * the mmap_sem hold in read mode to protect against MADV_DONTNEED and @@ -458,11 +470,17 @@ static inline int pmd_write(pmd_t pmd) * undefined so behaving like if the pmd was none is safe (because it * can return none anyway). The compiler level barrier() is critically * important to compute the two checks atomically on the same pmdval. + * + * For 32bit kernels with a 64bit large pmd_t this automatically takes + * care of reading the pmd atomically to avoid SMP race conditions + * against pmd_populate() when the mmap_sem is hold for reading by the + * caller (a special atomic read not done by "gcc" as in the generic + * version above, is also needed when THP is disabled because the page + * fault can populate the pmd from under us). */ static inline int pmd_none_or_trans_huge_or_clear_bad(pmd_t *pmd) { - /* depend on compiler for an atomic pmd read */ - pmd_t pmdval = *pmd; + pmd_t pmdval = pmd_read_atomic(pmd); /* * The barrier will stabilize the pmdval in a register or on * the stack so that it will stop changing under the code. -- cgit v1.2.3-70-g09d2 From bb8ac181a5cf50458a0d83b4460790badc9fdc16 Mon Sep 17 00:00:00 2001 From: Al Viro Date: Sat, 19 May 2012 10:25:23 -0400 Subject: bury __kernel_nlink_t, make internal nlink_t consistent Signed-off-by: Al Viro --- arch/alpha/include/asm/posix_types.h | 3 --- arch/arm/include/asm/posix_types.h | 3 --- arch/avr32/include/asm/posix_types.h | 3 --- arch/blackfin/include/asm/posix_types.h | 3 --- arch/cris/include/asm/posix_types.h | 3 --- arch/frv/include/asm/posix_types.h | 3 --- arch/h8300/include/asm/posix_types.h | 3 --- arch/ia64/include/asm/posix_types.h | 3 --- arch/m32r/include/asm/posix_types.h | 3 --- arch/m68k/include/asm/posix_types.h | 3 --- arch/mips/include/asm/posix_types.h | 5 ----- arch/mn10300/include/asm/posix_types.h | 3 --- arch/parisc/include/asm/posix_types.h | 3 --- arch/powerpc/include/asm/posix_types.h | 3 --- arch/s390/include/asm/posix_types.h | 3 --- arch/sh/include/asm/posix_types_32.h | 2 -- arch/sh/include/asm/posix_types_64.h | 2 -- arch/sparc/include/asm/posix_types.h | 5 ----- arch/tile/include/asm/compat.h | 1 - arch/x86/include/asm/posix_types_32.h | 3 --- include/asm-generic/posix_types.h | 4 ---- include/linux/types.h | 2 +- 22 files changed, 1 insertion(+), 65 deletions(-) (limited to 'include/asm-generic') diff --git a/arch/alpha/include/asm/posix_types.h b/arch/alpha/include/asm/posix_types.h index 24779fc95994..5a8a48320efe 100644 --- a/arch/alpha/include/asm/posix_types.h +++ b/arch/alpha/include/asm/posix_types.h @@ -10,9 +10,6 @@ typedef unsigned int __kernel_ino_t; #define __kernel_ino_t __kernel_ino_t -typedef unsigned int __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t - typedef unsigned long __kernel_sigset_t; /* at least 32 bits */ #include diff --git a/arch/arm/include/asm/posix_types.h b/arch/arm/include/asm/posix_types.h index efdf99045d87..d2de9cbbcd9b 100644 --- a/arch/arm/include/asm/posix_types.h +++ b/arch/arm/include/asm/posix_types.h @@ -22,9 +22,6 @@ typedef unsigned short __kernel_mode_t; #define __kernel_mode_t __kernel_mode_t -typedef unsigned short __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t - typedef unsigned short __kernel_ipc_pid_t; #define __kernel_ipc_pid_t __kernel_ipc_pid_t diff --git a/arch/avr32/include/asm/posix_types.h b/arch/avr32/include/asm/posix_types.h index 74667bfc88cc..9ba9e749b3f3 100644 --- a/arch/avr32/include/asm/posix_types.h +++ b/arch/avr32/include/asm/posix_types.h @@ -17,9 +17,6 @@ typedef unsigned short __kernel_mode_t; #define __kernel_mode_t __kernel_mode_t -typedef unsigned short __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t - typedef unsigned short __kernel_ipc_pid_t; #define __kernel_ipc_pid_t __kernel_ipc_pid_t diff --git a/arch/blackfin/include/asm/posix_types.h b/arch/blackfin/include/asm/posix_types.h index 41bc1875c4d7..1bd3436db6a7 100644 --- a/arch/blackfin/include/asm/posix_types.h +++ b/arch/blackfin/include/asm/posix_types.h @@ -10,9 +10,6 @@ typedef unsigned short __kernel_mode_t; #define __kernel_mode_t __kernel_mode_t -typedef unsigned short __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t - typedef unsigned int __kernel_ipc_pid_t; #define __kernel_ipc_pid_t __kernel_ipc_pid_t diff --git a/arch/cris/include/asm/posix_types.h b/arch/cris/include/asm/posix_types.h index 234891c74e2b..ce4e51793151 100644 --- a/arch/cris/include/asm/posix_types.h +++ b/arch/cris/include/asm/posix_types.h @@ -15,9 +15,6 @@ typedef unsigned short __kernel_mode_t; #define __kernel_mode_t __kernel_mode_t -typedef unsigned short __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t - typedef unsigned short __kernel_ipc_pid_t; #define __kernel_ipc_pid_t __kernel_ipc_pid_t diff --git a/arch/frv/include/asm/posix_types.h b/arch/frv/include/asm/posix_types.h index 3f34cb45fbb3..fe512af74a5a 100644 --- a/arch/frv/include/asm/posix_types.h +++ b/arch/frv/include/asm/posix_types.h @@ -10,9 +10,6 @@ typedef unsigned short __kernel_mode_t; #define __kernel_mode_t __kernel_mode_t -typedef unsigned short __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t - typedef unsigned short __kernel_ipc_pid_t; #define __kernel_ipc_pid_t __kernel_ipc_pid_t diff --git a/arch/h8300/include/asm/posix_types.h b/arch/h8300/include/asm/posix_types.h index bc4c34efb1ad..91e62ba4c7b0 100644 --- a/arch/h8300/include/asm/posix_types.h +++ b/arch/h8300/include/asm/posix_types.h @@ -10,9 +10,6 @@ typedef unsigned short __kernel_mode_t; #define __kernel_mode_t __kernel_mode_t -typedef unsigned short __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t - typedef unsigned short __kernel_ipc_pid_t; #define __kernel_ipc_pid_t __kernel_ipc_pid_t diff --git a/arch/ia64/include/asm/posix_types.h b/arch/ia64/include/asm/posix_types.h index 7323ab9467eb..99ee1d6510cf 100644 --- a/arch/ia64/include/asm/posix_types.h +++ b/arch/ia64/include/asm/posix_types.h @@ -1,9 +1,6 @@ #ifndef _ASM_IA64_POSIX_TYPES_H #define _ASM_IA64_POSIX_TYPES_H -typedef unsigned int __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t - typedef unsigned long __kernel_sigset_t; /* at least 32 bits */ #include diff --git a/arch/m32r/include/asm/posix_types.h b/arch/m32r/include/asm/posix_types.h index 0195850e1f88..236de26a409b 100644 --- a/arch/m32r/include/asm/posix_types.h +++ b/arch/m32r/include/asm/posix_types.h @@ -10,9 +10,6 @@ typedef unsigned short __kernel_mode_t; #define __kernel_mode_t __kernel_mode_t -typedef unsigned short __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t - typedef unsigned short __kernel_ipc_pid_t; #define __kernel_ipc_pid_t __kernel_ipc_pid_t diff --git a/arch/m68k/include/asm/posix_types.h b/arch/m68k/include/asm/posix_types.h index 6373093be72b..cf4dbf70fdc7 100644 --- a/arch/m68k/include/asm/posix_types.h +++ b/arch/m68k/include/asm/posix_types.h @@ -10,9 +10,6 @@ typedef unsigned short __kernel_mode_t; #define __kernel_mode_t __kernel_mode_t -typedef unsigned short __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t - typedef unsigned short __kernel_ipc_pid_t; #define __kernel_ipc_pid_t __kernel_ipc_pid_t diff --git a/arch/mips/include/asm/posix_types.h b/arch/mips/include/asm/posix_types.h index e0308dcca135..fa03ec3fbf89 100644 --- a/arch/mips/include/asm/posix_types.h +++ b/arch/mips/include/asm/posix_types.h @@ -17,11 +17,6 @@ * assume GCC is being used. */ -#if (_MIPS_SZLONG == 64) -typedef unsigned int __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t -#endif - typedef long __kernel_daddr_t; #define __kernel_daddr_t __kernel_daddr_t diff --git a/arch/mn10300/include/asm/posix_types.h b/arch/mn10300/include/asm/posix_types.h index ab506181ec31..d31eeea480cf 100644 --- a/arch/mn10300/include/asm/posix_types.h +++ b/arch/mn10300/include/asm/posix_types.h @@ -20,9 +20,6 @@ typedef unsigned short __kernel_mode_t; #define __kernel_mode_t __kernel_mode_t -typedef unsigned short __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t - typedef unsigned short __kernel_ipc_pid_t; #define __kernel_ipc_pid_t __kernel_ipc_pid_t diff --git a/arch/parisc/include/asm/posix_types.h b/arch/parisc/include/asm/posix_types.h index 5212b0357daf..b9344256f76b 100644 --- a/arch/parisc/include/asm/posix_types.h +++ b/arch/parisc/include/asm/posix_types.h @@ -10,9 +10,6 @@ typedef unsigned short __kernel_mode_t; #define __kernel_mode_t __kernel_mode_t -typedef unsigned short __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t - typedef unsigned short __kernel_ipc_pid_t; #define __kernel_ipc_pid_t __kernel_ipc_pid_t diff --git a/arch/powerpc/include/asm/posix_types.h b/arch/powerpc/include/asm/posix_types.h index f1393252bbda..2958c5b97b2d 100644 --- a/arch/powerpc/include/asm/posix_types.h +++ b/arch/powerpc/include/asm/posix_types.h @@ -16,9 +16,6 @@ typedef int __kernel_ssize_t; typedef long __kernel_ptrdiff_t; #define __kernel_size_t __kernel_size_t -typedef unsigned short __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t - typedef short __kernel_ipc_pid_t; #define __kernel_ipc_pid_t __kernel_ipc_pid_t #endif diff --git a/arch/s390/include/asm/posix_types.h b/arch/s390/include/asm/posix_types.h index edf8527ff08d..7be104c0f192 100644 --- a/arch/s390/include/asm/posix_types.h +++ b/arch/s390/include/asm/posix_types.h @@ -24,7 +24,6 @@ typedef unsigned short __kernel_old_dev_t; typedef unsigned long __kernel_ino_t; typedef unsigned short __kernel_mode_t; -typedef unsigned short __kernel_nlink_t; typedef unsigned short __kernel_ipc_pid_t; typedef unsigned short __kernel_uid_t; typedef unsigned short __kernel_gid_t; @@ -35,7 +34,6 @@ typedef int __kernel_ptrdiff_t; typedef unsigned int __kernel_ino_t; typedef unsigned int __kernel_mode_t; -typedef unsigned int __kernel_nlink_t; typedef int __kernel_ipc_pid_t; typedef unsigned int __kernel_uid_t; typedef unsigned int __kernel_gid_t; @@ -47,7 +45,6 @@ typedef unsigned long __kernel_sigset_t; /* at least 32 bits */ #define __kernel_ino_t __kernel_ino_t #define __kernel_mode_t __kernel_mode_t -#define __kernel_nlink_t __kernel_nlink_t #define __kernel_ipc_pid_t __kernel_ipc_pid_t #define __kernel_uid_t __kernel_uid_t #define __kernel_gid_t __kernel_gid_t diff --git a/arch/sh/include/asm/posix_types_32.h b/arch/sh/include/asm/posix_types_32.h index abda58467ece..ba0bdc423b07 100644 --- a/arch/sh/include/asm/posix_types_32.h +++ b/arch/sh/include/asm/posix_types_32.h @@ -3,8 +3,6 @@ typedef unsigned short __kernel_mode_t; #define __kernel_mode_t __kernel_mode_t -typedef unsigned short __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t typedef unsigned short __kernel_ipc_pid_t; #define __kernel_ipc_pid_t __kernel_ipc_pid_t typedef unsigned short __kernel_uid_t; diff --git a/arch/sh/include/asm/posix_types_64.h b/arch/sh/include/asm/posix_types_64.h index fcda07b4a616..244f7e950e17 100644 --- a/arch/sh/include/asm/posix_types_64.h +++ b/arch/sh/include/asm/posix_types_64.h @@ -3,8 +3,6 @@ typedef unsigned short __kernel_mode_t; #define __kernel_mode_t __kernel_mode_t -typedef unsigned short __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t typedef unsigned short __kernel_ipc_pid_t; #define __kernel_ipc_pid_t __kernel_ipc_pid_t typedef unsigned short __kernel_uid_t; diff --git a/arch/sparc/include/asm/posix_types.h b/arch/sparc/include/asm/posix_types.h index 3070f25ae90a..156220ed99eb 100644 --- a/arch/sparc/include/asm/posix_types.h +++ b/arch/sparc/include/asm/posix_types.h @@ -9,8 +9,6 @@ #if defined(__sparc__) && defined(__arch64__) /* sparc 64 bit */ -typedef unsigned int __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t typedef unsigned short __kernel_old_uid_t; typedef unsigned short __kernel_old_gid_t; @@ -38,9 +36,6 @@ typedef unsigned short __kernel_gid_t; typedef unsigned short __kernel_mode_t; #define __kernel_mode_t __kernel_mode_t -typedef short __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t - typedef long __kernel_daddr_t; #define __kernel_daddr_t __kernel_daddr_t diff --git a/arch/tile/include/asm/compat.h b/arch/tile/include/asm/compat.h index 69adc08d36a5..6e74450ff0a1 100644 --- a/arch/tile/include/asm/compat.h +++ b/arch/tile/include/asm/compat.h @@ -44,7 +44,6 @@ typedef __kernel_uid32_t __compat_gid32_t; typedef __kernel_mode_t compat_mode_t; typedef __kernel_dev_t compat_dev_t; typedef __kernel_loff_t compat_loff_t; -typedef __kernel_nlink_t compat_nlink_t; typedef __kernel_ipc_pid_t compat_ipc_pid_t; typedef __kernel_daddr_t compat_daddr_t; typedef __kernel_fsid_t compat_fsid_t; diff --git a/arch/x86/include/asm/posix_types_32.h b/arch/x86/include/asm/posix_types_32.h index 99f262e04b91..8e525059e7d8 100644 --- a/arch/x86/include/asm/posix_types_32.h +++ b/arch/x86/include/asm/posix_types_32.h @@ -10,9 +10,6 @@ typedef unsigned short __kernel_mode_t; #define __kernel_mode_t __kernel_mode_t -typedef unsigned short __kernel_nlink_t; -#define __kernel_nlink_t __kernel_nlink_t - typedef unsigned short __kernel_ipc_pid_t; #define __kernel_ipc_pid_t __kernel_ipc_pid_t diff --git a/include/asm-generic/posix_types.h b/include/asm-generic/posix_types.h index 91d44bd4dde3..fe74fccf18db 100644 --- a/include/asm-generic/posix_types.h +++ b/include/asm-generic/posix_types.h @@ -23,10 +23,6 @@ typedef __kernel_ulong_t __kernel_ino_t; typedef unsigned int __kernel_mode_t; #endif -#ifndef __kernel_nlink_t -typedef __kernel_ulong_t __kernel_nlink_t; -#endif - #ifndef __kernel_pid_t typedef int __kernel_pid_t; #endif diff --git a/include/linux/types.h b/include/linux/types.h index 7f480db60231..9c1bd539ea70 100644 --- a/include/linux/types.h +++ b/include/linux/types.h @@ -25,7 +25,7 @@ typedef __kernel_dev_t dev_t; typedef __kernel_ino_t ino_t; typedef __kernel_mode_t mode_t; typedef unsigned short umode_t; -typedef __kernel_nlink_t nlink_t; +typedef __u32 nlink_t; typedef __kernel_off_t off_t; typedef __kernel_pid_t pid_t; typedef __kernel_daddr_t daddr_t; -- cgit v1.2.3-70-g09d2 From 133fd9f5cda2d86904126f4b9fa4e8f4330c9569 Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Thu, 31 May 2012 16:26:08 -0700 Subject: vsprintf: further optimize decimal conversion Previous code was using optimizations which were developed to work well even on narrow-word CPUs (by today's standards). But Linux runs only on 32-bit and wider CPUs. We can use that. First: using 32x32->64 multiply and trivial 32-bit shift, we can correctly divide by 10 much larger numbers, and thus we can print groups of 9 digits instead of groups of 5 digits. Next: there are two algorithms to print larger numbers. One is generic: divide by 1000000000 and repeatedly print groups of (up to) 9 digits. It's conceptually simple, but requires an (unsigned long long) / 1000000000 division. Second algorithm splits 64-bit unsigned long long into 16-bit chunks, manipulates them cleverly and generates groups of 4 decimal digits. It so happens that it does NOT require long long division. If long is > 32 bits, division of 64-bit values is relatively easy, and we will use the first algorithm. If long long is > 64 bits (strange architecture with VERY large long long), second algorithm can't be used, and we again use the first one. Else (if long is 32 bits and long long is 64 bits) we use second one. And third: there is a simple optimization which takes fast path not only for zero as was done before, but for all one-digit numbers. In all tested cases new code is faster than old one, in many cases by 30%, in few cases by more than 50% (for example, on x86-32, conversion of 12345678). Code growth is ~0 in 32-bit case and ~130 bytes in 64-bit case. This patch is based upon an original from Michal Nazarewicz. [akpm@linux-foundation.org: checkpatch fixes] Signed-off-by: Michal Nazarewicz Signed-off-by: Denys Vlasenko Cc: Douglas W Jones Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/asm-generic/bitsperlong.h | 4 + lib/vsprintf.c | 281 ++++++++++++++++++++++++++------------ 2 files changed, 194 insertions(+), 91 deletions(-) (limited to 'include/asm-generic') diff --git a/include/asm-generic/bitsperlong.h b/include/asm-generic/bitsperlong.h index 4ae54e07de83..a7b0914348fd 100644 --- a/include/asm-generic/bitsperlong.h +++ b/include/asm-generic/bitsperlong.h @@ -28,5 +28,9 @@ #error Inconsistent word size. Check asm/bitsperlong.h #endif +#ifndef BITS_PER_LONG_LONG +#define BITS_PER_LONG_LONG 64 +#endif + #endif /* __KERNEL__ */ #endif /* __ASM_GENERIC_BITS_PER_LONG */ diff --git a/lib/vsprintf.c b/lib/vsprintf.c index b8fbd275bc46..c3f36d415bdf 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -112,106 +112,199 @@ int skip_atoi(const char **s) /* Decimal conversion is by far the most typical, and is used * for /proc and /sys data. This directly impacts e.g. top performance * with many processes running. We optimize it for speed - * using code from - * http://www.cs.uiowa.edu/~jones/bcd/decimal.html - * (with permission from the author, Douglas W. Jones). */ + * using ideas described at + * (with permission from the author, Douglas W. Jones). + */ -/* Formats correctly any integer in [0,99999]. - * Outputs from one to five digits depending on input. - * On i386 gcc 4.1.2 -O2: ~250 bytes of code. */ +#if BITS_PER_LONG != 32 || BITS_PER_LONG_LONG != 64 +/* Formats correctly any integer in [0, 999999999] */ static noinline_for_stack -char *put_dec_trunc(char *buf, unsigned q) +char *put_dec_full9(char *buf, unsigned q) { - unsigned d3, d2, d1, d0; - d1 = (q>>4) & 0xf; - d2 = (q>>8) & 0xf; - d3 = (q>>12); - - d0 = 6*(d3 + d2 + d1) + (q & 0xf); - q = (d0 * 0xcd) >> 11; - d0 = d0 - 10*q; - *buf++ = d0 + '0'; /* least significant digit */ - d1 = q + 9*d3 + 5*d2 + d1; - if (d1 != 0) { - q = (d1 * 0xcd) >> 11; - d1 = d1 - 10*q; - *buf++ = d1 + '0'; /* next digit */ - - d2 = q + 2*d2; - if ((d2 != 0) || (d3 != 0)) { - q = (d2 * 0xd) >> 7; - d2 = d2 - 10*q; - *buf++ = d2 + '0'; /* next digit */ - - d3 = q + 4*d3; - if (d3 != 0) { - q = (d3 * 0xcd) >> 11; - d3 = d3 - 10*q; - *buf++ = d3 + '0'; /* next digit */ - if (q != 0) - *buf++ = q + '0'; /* most sign. digit */ - } - } - } + unsigned r; + /* + * Possible ways to approx. divide by 10 + * (x * 0x1999999a) >> 32 x < 1073741829 (multiply must be 64-bit) + * (x * 0xcccd) >> 19 x < 81920 (x < 262149 when 64-bit mul) + * (x * 0x6667) >> 18 x < 43699 + * (x * 0x3334) >> 17 x < 16389 + * (x * 0x199a) >> 16 x < 16389 + * (x * 0x0ccd) >> 15 x < 16389 + * (x * 0x0667) >> 14 x < 2739 + * (x * 0x0334) >> 13 x < 1029 + * (x * 0x019a) >> 12 x < 1029 + * (x * 0x00cd) >> 11 x < 1029 shorter code than * 0x67 (on i386) + * (x * 0x0067) >> 10 x < 179 + * (x * 0x0034) >> 9 x < 69 same + * (x * 0x001a) >> 8 x < 69 same + * (x * 0x000d) >> 7 x < 69 same, shortest code (on i386) + * (x * 0x0007) >> 6 x < 19 + * See + */ + r = (q * (uint64_t)0x1999999a) >> 32; + *buf++ = (q - 10 * r) + '0'; /* 1 */ + q = (r * (uint64_t)0x1999999a) >> 32; + *buf++ = (r - 10 * q) + '0'; /* 2 */ + r = (q * (uint64_t)0x1999999a) >> 32; + *buf++ = (q - 10 * r) + '0'; /* 3 */ + q = (r * (uint64_t)0x1999999a) >> 32; + *buf++ = (r - 10 * q) + '0'; /* 4 */ + r = (q * (uint64_t)0x1999999a) >> 32; + *buf++ = (q - 10 * r) + '0'; /* 5 */ + /* Now value is under 10000, can avoid 64-bit multiply */ + q = (r * 0x199a) >> 16; + *buf++ = (r - 10 * q) + '0'; /* 6 */ + r = (q * 0xcd) >> 11; + *buf++ = (q - 10 * r) + '0'; /* 7 */ + q = (r * 0xcd) >> 11; + *buf++ = (r - 10 * q) + '0'; /* 8 */ + *buf++ = q + '0'; /* 9 */ return buf; } -/* Same with if's removed. Always emits five digits */ +#endif + +/* Similar to above but do not pad with zeros. + * Code can be easily arranged to print 9 digits too, but our callers + * always call put_dec_full9() instead when the number has 9 decimal digits. + */ static noinline_for_stack -char *put_dec_full(char *buf, unsigned q) +char *put_dec_trunc8(char *buf, unsigned r) { - /* BTW, if q is in [0,9999], 8-bit ints will be enough, */ - /* but anyway, gcc produces better code with full-sized ints */ - unsigned d3, d2, d1, d0; - d1 = (q>>4) & 0xf; - d2 = (q>>8) & 0xf; - d3 = (q>>12); + unsigned q; + + /* Copy of previous function's body with added early returns */ + q = (r * (uint64_t)0x1999999a) >> 32; + *buf++ = (r - 10 * q) + '0'; /* 2 */ + if (q == 0) + return buf; + r = (q * (uint64_t)0x1999999a) >> 32; + *buf++ = (q - 10 * r) + '0'; /* 3 */ + if (r == 0) + return buf; + q = (r * (uint64_t)0x1999999a) >> 32; + *buf++ = (r - 10 * q) + '0'; /* 4 */ + if (q == 0) + return buf; + r = (q * (uint64_t)0x1999999a) >> 32; + *buf++ = (q - 10 * r) + '0'; /* 5 */ + if (r == 0) + return buf; + q = (r * 0x199a) >> 16; + *buf++ = (r - 10 * q) + '0'; /* 6 */ + if (q == 0) + return buf; + r = (q * 0xcd) >> 11; + *buf++ = (q - 10 * r) + '0'; /* 7 */ + if (r == 0) + return buf; + q = (r * 0xcd) >> 11; + *buf++ = (r - 10 * q) + '0'; /* 8 */ + if (q == 0) + return buf; + *buf++ = q + '0'; /* 9 */ + return buf; +} - /* - * Possible ways to approx. divide by 10 - * gcc -O2 replaces multiply with shifts and adds - * (x * 0xcd) >> 11: 11001101 - shorter code than * 0x67 (on i386) - * (x * 0x67) >> 10: 1100111 - * (x * 0x34) >> 9: 110100 - same - * (x * 0x1a) >> 8: 11010 - same - * (x * 0x0d) >> 7: 1101 - same, shortest code (on i386) - */ - d0 = 6*(d3 + d2 + d1) + (q & 0xf); - q = (d0 * 0xcd) >> 11; - d0 = d0 - 10*q; - *buf++ = d0 + '0'; - d1 = q + 9*d3 + 5*d2 + d1; - q = (d1 * 0xcd) >> 11; - d1 = d1 - 10*q; - *buf++ = d1 + '0'; - - d2 = q + 2*d2; - q = (d2 * 0xd) >> 7; - d2 = d2 - 10*q; - *buf++ = d2 + '0'; - - d3 = q + 4*d3; - q = (d3 * 0xcd) >> 11; /* - shorter code */ - /* q = (d3 * 0x67) >> 10; - would also work */ - d3 = d3 - 10*q; - *buf++ = d3 + '0'; - *buf++ = q + '0'; +/* There are two algorithms to print larger numbers. + * One is generic: divide by 1000000000 and repeatedly print + * groups of (up to) 9 digits. It's conceptually simple, + * but requires a (unsigned long long) / 1000000000 division. + * + * Second algorithm splits 64-bit unsigned long long into 16-bit chunks, + * manipulates them cleverly and generates groups of 4 decimal digits. + * It so happens that it does NOT require long long division. + * + * If long is > 32 bits, division of 64-bit values is relatively easy, + * and we will use the first algorithm. + * If long long is > 64 bits (strange architecture with VERY large long long), + * second algorithm can't be used, and we again use the first one. + * + * Else (if long is 32 bits and long long is 64 bits) we use second one. + */ - return buf; +#if BITS_PER_LONG != 32 || BITS_PER_LONG_LONG != 64 + +/* First algorithm: generic */ + +static +char *put_dec(char *buf, unsigned long long n) +{ + if (n >= 100*1000*1000) { + while (n >= 1000*1000*1000) + buf = put_dec_full9(buf, do_div(n, 1000*1000*1000)); + if (n >= 100*1000*1000) + return put_dec_full9(buf, n); + } + return put_dec_trunc8(buf, n); } -/* No inlining helps gcc to use registers better */ + +#else + +/* Second algorithm: valid only for 64-bit long longs */ + static noinline_for_stack -char *put_dec(char *buf, unsigned long long num) +char *put_dec_full4(char *buf, unsigned q) { - while (1) { - unsigned rem; - if (num < 100000) - return put_dec_trunc(buf, num); - rem = do_div(num, 100000); - buf = put_dec_full(buf, rem); - } + unsigned r; + r = (q * 0xcccd) >> 19; + *buf++ = (q - 10 * r) + '0'; + q = (r * 0x199a) >> 16; + *buf++ = (r - 10 * q) + '0'; + r = (q * 0xcd) >> 11; + *buf++ = (q - 10 * r) + '0'; + *buf++ = r + '0'; + return buf; +} + +/* Based on code by Douglas W. Jones found at + * + * (with permission from the author). + * Performs no 64-bit division and hence should be fast on 32-bit machines. + */ +static +char *put_dec(char *buf, unsigned long long n) +{ + uint32_t d3, d2, d1, q, h; + + if (n < 100*1000*1000) + return put_dec_trunc8(buf, n); + + d1 = ((uint32_t)n >> 16); /* implicit "& 0xffff" */ + h = (n >> 32); + d2 = (h ) & 0xffff; + d3 = (h >> 16); /* implicit "& 0xffff" */ + + q = 656 * d3 + 7296 * d2 + 5536 * d1 + ((uint32_t)n & 0xffff); + + buf = put_dec_full4(buf, q % 10000); + q = q / 10000; + + d1 = q + 7671 * d3 + 9496 * d2 + 6 * d1; + buf = put_dec_full4(buf, d1 % 10000); + q = d1 / 10000; + + d2 = q + 4749 * d3 + 42 * d2; + buf = put_dec_full4(buf, d2 % 10000); + q = d2 / 10000; + + d3 = q + 281 * d3; + if (!d3) + goto done; + buf = put_dec_full4(buf, d3 % 10000); + q = d3 / 10000; + if (!q) + goto done; + buf = put_dec_full4(buf, q); + done: + while (buf[-1] == '0') + --buf; + + return buf; } +#endif + /* * Convert passed number to decimal string. * Returns the length of string. On buffer overflow, returns 0. @@ -220,16 +313,22 @@ char *put_dec(char *buf, unsigned long long num) */ int num_to_str(char *buf, int size, unsigned long long num) { - char tmp[21]; /* Enough for 2^64 in decimal */ + char tmp[sizeof(num) * 3]; int idx, len; - len = put_dec(tmp, num) - tmp; + /* put_dec() may work incorrectly for num = 0 (generate "", not "0") */ + if (num <= 9) { + tmp[0] = '0' + num; + len = 1; + } else { + len = put_dec(tmp, num) - tmp; + } if (len > size) return 0; for (idx = 0; idx < len; ++idx) buf[idx] = tmp[len - idx - 1]; - return len; + return len; } #define ZEROPAD 1 /* pad with zero */ @@ -314,8 +413,8 @@ char *number(char *buf, char *end, unsigned long long num, /* generate full string in tmp[], in reverse order */ i = 0; - if (num == 0) - tmp[i++] = '0'; + if (num < spec.base) + tmp[i++] = digits[num] | locase; /* Generic code, for any base: else do { tmp[i++] = (digits[do_div(num,base)] | locase); @@ -611,7 +710,7 @@ char *ip4_string(char *p, const u8 *addr, const char *fmt) } for (i = 0; i < 4; i++) { char temp[3]; /* hold each IP quad in reverse order */ - int digits = put_dec_trunc(temp, addr[index]) - temp; + int digits = put_dec_trunc8(temp, addr[index]) - temp; if (leading_zeros) { if (digits < 3) *p++ = '0'; -- cgit v1.2.3-70-g09d2