From f8d4cbe40b2cfd3d1ad66afb621c5291ad74eafd Mon Sep 17 00:00:00 2001 From: Kent Overstreet Date: Thu, 21 May 2020 17:19:47 -0400 Subject: Update log2.h from linux kernel This fixes a build breakage where the old log2.g referenced __ilog2_NaN() which we weren't defining. --- include/linux/log2.h | 200 +++++++++++++++++++++++++++++++++++---------------- 1 file changed, 140 insertions(+), 60 deletions(-) (limited to 'include/linux/log2.h') diff --git a/include/linux/log2.h b/include/linux/log2.h index 2bbe25e4..f031ea12 100644 --- a/include/linux/log2.h +++ b/include/linux/log2.h @@ -1,30 +1,15 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ /* Integer base 2 logarithm calculation * * Copyright (C) 2006 Red Hat, Inc. All Rights Reserved. * Written by David Howells (dhowells@redhat.com) - * - * 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 option) any later version. */ -#ifndef _TOOLS_LINUX_LOG2_H -#define _TOOLS_LINUX_LOG2_H - -#include -#ifndef PAGE_SHIFT -#define PAGE_SHIFT ilog2(PAGE_SIZE) -#endif +#ifndef _LINUX_LOG2_H +#define _LINUX_LOG2_H +#include #include -#include - -/* - * deal with unrepresentable constant logarithms - */ -extern __attribute__((const)) -int ____ilog2_NaN(void); /* * non-constant log of base 2 calculators @@ -32,31 +17,39 @@ int ____ilog2_NaN(void); * more efficiently than using fls() and fls64() * - the arch is not required to handle n==0 if implementing the fallback */ +#ifndef CONFIG_ARCH_HAS_ILOG2_U32 static inline __attribute__((const)) int __ilog2_u32(u32 n) { return fls(n) - 1; } +#endif +#ifndef CONFIG_ARCH_HAS_ILOG2_U64 static inline __attribute__((const)) int __ilog2_u64(u64 n) { return fls64(n) - 1; } +#endif -/* - * Determine whether some value is a power of two, where zero is +/** + * is_power_of_2() - check if a value is a power of two + * @n: the value to check + * + * Determine whether some value is a power of two, where zero is * *not* considered a power of two. + * Return: true if @n is a power of 2, otherwise false. */ - static inline __attribute__((const)) bool is_power_of_2(unsigned long n) { return (n != 0 && ((n & (n - 1)) == 0)); } -/* - * round up to nearest power of two +/** + * __roundup_pow_of_two() - round up to nearest power of two + * @n: value to round up */ static inline __attribute__((const)) unsigned long __roundup_pow_of_two(unsigned long n) @@ -64,8 +57,9 @@ unsigned long __roundup_pow_of_two(unsigned long n) return 1UL << fls_long(n - 1); } -/* - * round down to nearest power of two +/** + * __rounddown_pow_of_two() - round down to nearest power of two + * @n: value to round down */ static inline __attribute__((const)) unsigned long __rounddown_pow_of_two(unsigned long n) @@ -74,19 +68,16 @@ unsigned long __rounddown_pow_of_two(unsigned long n) } /** - * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value - * @n - parameter - * - * constant-capable log of base 2 calculation - * - this can be used to initialise global variables from constant data, hence - * the massive ternary operator construction + * const_ilog2 - log base 2 of 32-bit or a 64-bit constant unsigned value + * @n: parameter * - * selects the appropriately-sized optimised version depending on sizeof(n) + * Use this where sparse expects a true constant expression, e.g. for array + * indices. */ -#define ilog2(n) \ +#define const_ilog2(n) \ ( \ __builtin_constant_p(n) ? ( \ - (n) < 1 ? ____ilog2_NaN() : \ + (n) < 2 ? 0 : \ (n) & (1ULL << 63) ? 63 : \ (n) & (1ULL << 62) ? 62 : \ (n) & (1ULL << 61) ? 61 : \ @@ -149,18 +140,31 @@ unsigned long __rounddown_pow_of_two(unsigned long n) (n) & (1ULL << 4) ? 4 : \ (n) & (1ULL << 3) ? 3 : \ (n) & (1ULL << 2) ? 2 : \ - (n) & (1ULL << 1) ? 1 : \ - (n) & (1ULL << 0) ? 0 : \ - ____ilog2_NaN() \ - ) : \ - (sizeof(n) <= 4) ? \ - __ilog2_u32(n) : \ - __ilog2_u64(n) \ + 1) : \ + -1) + +/** + * ilog2 - log base 2 of 32-bit or a 64-bit unsigned value + * @n: parameter + * + * constant-capable log of base 2 calculation + * - this can be used to initialise global variables from constant data, hence + * the massive ternary operator construction + * + * selects the appropriately-sized optimised version depending on sizeof(n) + */ +#define ilog2(n) \ +( \ + __builtin_constant_p(n) ? \ + const_ilog2(n) : \ + (sizeof(n) <= 4) ? \ + __ilog2_u32(n) : \ + __ilog2_u64(n) \ ) /** * roundup_pow_of_two - round the given value up to nearest power of two - * @n - parameter + * @n: parameter * * round the given value up to the nearest power of two * - the result is undefined when n == 0 @@ -177,7 +181,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n) /** * rounddown_pow_of_two - round the given value down to nearest power of two - * @n - parameter + * @n: parameter * * round the given value down to the nearest power of two * - the result is undefined when n == 0 @@ -190,29 +194,105 @@ unsigned long __rounddown_pow_of_two(unsigned long n) __rounddown_pow_of_two(n) \ ) +static inline __attribute_const__ +int __order_base_2(unsigned long n) +{ + return n > 1 ? ilog2(n - 1) + 1 : 0; +} + +/** + * order_base_2 - calculate the (rounded up) base 2 order of the argument + * @n: parameter + * + * The first few values calculated by this routine: + * ob2(0) = 0 + * ob2(1) = 0 + * ob2(2) = 1 + * ob2(3) = 2 + * ob2(4) = 2 + * ob2(5) = 3 + * ... and so on. + */ +#define order_base_2(n) \ +( \ + __builtin_constant_p(n) ? ( \ + ((n) == 0 || (n) == 1) ? 0 : \ + ilog2((n) - 1) + 1) : \ + __order_base_2(n) \ +) + static inline __attribute__((const)) -int __get_order(unsigned long size) +int __bits_per(unsigned long n) +{ + if (n < 2) + return 1; + if (is_power_of_2(n)) + return order_base_2(n) + 1; + return order_base_2(n); +} + +/** + * bits_per - calculate the number of bits required for the argument + * @n: parameter + * + * This is constant-capable and can be used for compile time + * initializations, e.g bitfields. + * + * The first few values calculated by this routine: + * bf(0) = 1 + * bf(1) = 1 + * bf(2) = 2 + * bf(3) = 2 + * bf(4) = 3 + * ... and so on. + */ +#define bits_per(n) \ +( \ + __builtin_constant_p(n) ? ( \ + ((n) == 0 || (n) == 1) \ + ? 1 : ilog2(n) + 1 \ + ) : \ + __bits_per(n) \ +) + +/** + * get_order - Determine the allocation order of a memory size + * @size: The size for which to get the order + * + * Determine the allocation order of a particular sized block of memory. This + * is on a logarithmic scale, where: + * + * 0 -> 2^0 * PAGE_SIZE and below + * 1 -> 2^1 * PAGE_SIZE to 2^0 * PAGE_SIZE + 1 + * 2 -> 2^2 * PAGE_SIZE to 2^1 * PAGE_SIZE + 1 + * 3 -> 2^3 * PAGE_SIZE to 2^2 * PAGE_SIZE + 1 + * 4 -> 2^4 * PAGE_SIZE to 2^3 * PAGE_SIZE + 1 + * ... + * + * The order returned is used to find the smallest allocation granule required + * to hold an object of the specified size. + * + * The result is undefined if the size is 0. + */ +static inline __attribute_const__ int get_order(unsigned long size) { - int order; + if (__builtin_constant_p(size)) { + if (!size) + return BITS_PER_LONG - PAGE_SHIFT; + + if (size < (1UL << PAGE_SHIFT)) + return 0; + + return ilog2((size) - 1) - PAGE_SHIFT + 1; + } size--; size >>= PAGE_SHIFT; #if BITS_PER_LONG == 32 - order = fls(size); + return fls(size); #else - order = fls64(size); + return fls64(size); #endif - return order; } -#define get_order(n) \ -( \ - __builtin_constant_p(n) ? ( \ - ((n) == 0UL) ? BITS_PER_LONG - PAGE_SHIFT : \ - (((n) < (1UL << PAGE_SHIFT)) ? 0 : \ - ilog2((n) - 1) - PAGE_SHIFT + 1) \ - ) : \ - __get_order(n) \ -) - -#endif /* _TOOLS_LINUX_LOG2_H */ +#endif /* _LINUX_LOG2_H */ -- cgit v1.2.3