summaryrefslogtreecommitdiffstats
path: root/module/splat/splat-generic.c
diff options
context:
space:
mode:
authorBrian Behlendorf <[email protected]>2010-07-12 12:38:34 -0700
committerBrian Behlendorf <[email protected]>2010-07-13 16:44:02 -0700
commita4bfd8ea1b58d8797ec91b18982de243675e63bc (patch)
tree7506e0415944aa3c689610753900cbe0d143cf53 /module/splat/splat-generic.c
parentd466208f1e76c80fe14751739273b1932c4329f3 (diff)
Add __divdi3(), remove __udivdi3() kernel dependency
Up until now no SPL consumer attempted to perform signed 64-bit division so there was no need to support this. That has now changed so I adding 64-bit division support for 32-bit platforms. The signed implementation is based on the unsigned version. Since the have been several bug reports in the past concerning correct 64-bit division on 32-bit platforms I added some long over due regression tests. Much to my surprise the unsigned 64-bit division regression tests failed. This was surprising because __udivdi3() was implemented by simply calling div64_u64() which is provided by the kernel. This meant that the linux kernels 64-bit division algorithm on 32-bit platforms was flawed. After some investigation this turned out to be exactly the case. Because of this I was forced to abandon the kernel helper and instead to fully implement 64-bit division in the spl. There are several published implementation out there on how to do this properly and I settled on one proposed in the book Hacker's Delight. Their proposed algoritm is freely available without restriction and I have just modified it to be linux kernel friendly. The update implementation now passed all the unsigned and signed regression tests. This should be functional, but not fast, which is good enough for out purposes. If you want fast too I'd strongly suggest you upgrade to a 64-bit platform. I have also reported the kernel bug and we'll see if we can't get it fixed up stream.
Diffstat (limited to 'module/splat/splat-generic.c')
-rw-r--r--module/splat/splat-generic.c133
1 files changed, 133 insertions, 0 deletions
diff --git a/module/splat/splat-generic.c b/module/splat/splat-generic.c
index 8ad6913c0..f9c3c7ec5 100644
--- a/module/splat/splat-generic.c
+++ b/module/splat/splat-generic.c
@@ -45,6 +45,14 @@
#define SPLAT_GENERIC_TEST4_NAME "ddi_strtoll"
#define SPLAT_GENERIC_TEST4_DESC "ddi_strtoll Test"
+# define SPLAT_GENERIC_TEST5_ID 0x0d05
+# define SPLAT_GENERIC_TEST5_NAME "udivdi3"
+# define SPLAT_GENERIC_TEST5_DESC "Unsigned Div-64 Test"
+
+# define SPLAT_GENERIC_TEST6_ID 0x0d06
+# define SPLAT_GENERIC_TEST6_NAME "divdi3"
+# define SPLAT_GENERIC_TEST6_DESC "Signed Div-64 Test"
+
#define STR_POS "123456789"
#define STR_NEG "-123456789"
#define STR_BASE "0xabcdef"
@@ -183,6 +191,125 @@ define_splat_generic_test_strtox(l, long);
define_splat_generic_test_strtox(ull, unsigned long long);
define_splat_generic_test_strtox(ll, long long);
+/*
+ * The entries in the table are used in all combinations and the
+ * return value is checked to ensure it is range. On 32-bit
+ * systems __udivdi3 will be invoked for the 64-bit division.
+ * On 64-bit system the native 64-bit divide will be used so
+ * __udivdi3 isn't used but we might as well stil run the test.
+ */
+static int
+splat_generic_test_udivdi3(struct file *file, void *arg)
+{
+ const uint64_t tabu[] = {
+ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
+ 10, 11, 12, 13, 14, 15, 16, 1000, 2003,
+ 32765, 32766, 32767, 32768, 32769, 32760,
+ 65533, 65534, 65535, 65536, 65537, 65538,
+ 0x7ffffffeULL, 0x7fffffffULL, 0x80000000ULL, 0x80000001ULL,
+ 0x7000000000000000ULL, 0x7000000080000000ULL, 0x7000000080000001ULL,
+ 0x7fffffffffffffffULL, 0x7fffffff8fffffffULL, 0x7fffffff8ffffff1ULL,
+ 0x7fffffff00000000ULL, 0x7fffffff80000000ULL, 0x7fffffff00000001ULL,
+ 0x8000000000000000ULL, 0x8000000080000000ULL, 0x8000000080000001ULL,
+ 0xc000000000000000ULL, 0xc000000080000000ULL, 0xc000000080000001ULL,
+ 0xfffffffffffffffdULL, 0xfffffffffffffffeULL, 0xffffffffffffffffULL,
+ };
+ uint64_t uu, vu, qu, ru;
+ int n, i, j, errors = 0;
+
+ splat_vprint(file, SPLAT_GENERIC_TEST5_NAME, "%s",
+ "Testing unsigned 64-bit division.\n");
+ n = sizeof(tabu) / sizeof(tabu[0]);
+ for (i = 0; i < n; i++) {
+ for (j = 1; j < n; j++) {
+ uu = tabu[i];
+ vu = tabu[j];
+ qu = uu / vu; /* __udivdi3 */
+ ru = uu - qu * vu;
+ if (qu > uu || ru >= vu) {
+ splat_vprint(file, SPLAT_GENERIC_TEST5_NAME,
+ "%016llx/%016llx != %016llx rem %016llx\n",
+ uu, vu, qu, ru);
+ errors++;
+ }
+ }
+ }
+
+ if (errors) {
+ splat_vprint(file, SPLAT_GENERIC_TEST5_NAME,
+ "Failed %d/%d tests\n", errors, n * (n - 1));
+ return -ERANGE;
+ }
+
+ splat_vprint(file, SPLAT_GENERIC_TEST5_NAME,
+ "Passed all %d tests\n", n * (n - 1));
+
+ return 0;
+}
+
+/*
+ * The entries the table are used in all combinations, with + and - signs
+ * preceding them. The return value is checked to ensure it is range.
+ * On 32-bit systems __divdi3 will be invoked for the 64-bit division.
+ * On 64-bit system the native 64-bit divide will be used so __divdi3
+ * isn't used but we might as well stil run the test.
+ */
+static int
+splat_generic_test_divdi3(struct file *file, void *arg)
+{
+ const int64_t tabs[] = {
+ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
+ 10, 11, 12, 13, 14, 15, 16, 1000, 2003,
+ 32765, 32766, 32767, 32768, 32769, 32760,
+ 65533, 65534, 65535, 65536, 65537, 65538,
+ 0x7ffffffeLL, 0x7fffffffLL, 0x80000000LL, 0x80000001LL,
+ 0x7000000000000000LL, 0x7000000080000000LL, 0x7000000080000001LL,
+ 0x7fffffffffffffffLL, 0x7fffffff8fffffffLL, 0x7fffffff8ffffff1LL,
+ 0x7fffffff00000000LL, 0x7fffffff80000000LL, 0x7fffffff00000001LL,
+ 0x0123456789abcdefLL, 0x00000000abcdef01LL, 0x0000000012345678LL,
+#if BITS_PER_LONG == 32
+ 0x8000000000000000LL, 0x8000000080000000LL, 0x8000000080000001LL,
+#endif
+ };
+ int64_t u, v, q, r;
+ int n, i, j, k, errors = 0;
+
+ splat_vprint(file, SPLAT_GENERIC_TEST6_NAME, "%s",
+ "Testing signed 64-bit division.\n");
+ n = sizeof(tabs) / sizeof(tabs[0]);
+ for (i = 0; i < n; i++) {
+ for (j = 1; j < n; j++) {
+ for (k = 0; k <= 3; k++) {
+ u = (k & 1) ? -tabs[i] : tabs[i];
+ v = (k >= 2) ? -tabs[j] : tabs[j];
+
+ q = u / v; /* __divdi3 */
+ r = u - q * v;
+ if (abs64(q) > abs64(u) ||
+ abs64(r) >= abs64(v) ||
+ (r != 0 && (r ^ u) < 0)) {
+ splat_vprint(file,
+ SPLAT_GENERIC_TEST6_NAME,
+ "%016llx/%016llx != %016llx "
+ "rem %016llx\n", u, v, q, r);
+ errors++;
+ }
+ }
+ }
+ }
+
+ if (errors) {
+ splat_vprint(file, SPLAT_GENERIC_TEST6_NAME,
+ "Failed %d/%d tests\n", errors, n * (n - 1));
+ return -ERANGE;
+ }
+
+ splat_vprint(file, SPLAT_GENERIC_TEST6_NAME,
+ "Passed all %d tests\n", n * (n - 1));
+
+ return 0;
+}
+
splat_subsystem_t *
splat_generic_init(void)
{
@@ -208,6 +335,10 @@ splat_generic_init(void)
SPLAT_GENERIC_TEST3_ID, splat_generic_test_strtoull);
SPLAT_TEST_INIT(sub, SPLAT_GENERIC_TEST4_NAME, SPLAT_GENERIC_TEST4_DESC,
SPLAT_GENERIC_TEST4_ID, splat_generic_test_strtoll);
+ SPLAT_TEST_INIT(sub, SPLAT_GENERIC_TEST5_NAME, SPLAT_GENERIC_TEST5_DESC,
+ SPLAT_GENERIC_TEST5_ID, splat_generic_test_udivdi3);
+ SPLAT_TEST_INIT(sub, SPLAT_GENERIC_TEST6_NAME, SPLAT_GENERIC_TEST6_DESC,
+ SPLAT_GENERIC_TEST6_ID, splat_generic_test_divdi3);
return sub;
}
@@ -217,6 +348,8 @@ splat_generic_fini(splat_subsystem_t *sub)
{
ASSERT(sub);
+ SPLAT_TEST_FINI(sub, SPLAT_GENERIC_TEST6_ID);
+ SPLAT_TEST_FINI(sub, SPLAT_GENERIC_TEST5_ID);
SPLAT_TEST_FINI(sub, SPLAT_GENERIC_TEST4_ID);
SPLAT_TEST_FINI(sub, SPLAT_GENERIC_TEST3_ID);
SPLAT_TEST_FINI(sub, SPLAT_GENERIC_TEST2_ID);